Докажите что числа 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 взаимно простые.