Докажите что числа 364 и 495 взаимно простые

К задаче: доказать, что 364 и 495 взаимно простые (gcd(364,495) = 1). Способ 1: Евклидов алгоритм (по шагам) 1) 495 = 1·364 + 131 2) 364 = 2·131 + 102 3) 131 = 1·102 + 29 4) 102 = 3·29 + 15 5) 29 = 1·15 + 14 6) 15 = 1·14 + 1 7) 14 = 14·1 + 0 Последняя ненулевая остатка — 1, значит gcd(364,495) = 1. Таким образом, числа взаимно простые. Дополнительно (Bezout): можно увидеть, что 1 можно записать как линейную комбинацию 364 и 495 1 = 34·364 − 25·495 Это подтверждает, что наибольший общий делитель действительно равен 1 и что 364 и 495 не имеют общих простых делителей. Заключение: числа 364 и 495 взаимно простые.