№ 8. Докажите, что числа 644 и 495 — взаимно простые.

Применим алгоритм Евклида:

\(644=495\cdot1+149\);
\(495=149\cdot3+48\);
\(149=48\cdot3+5\);
\(48=5\cdot9+3\);
\(5=3\cdot1+2\);
\(3=2\cdot1+1\).

Последний ненулевой остаток равен 1, значит, \(\gcd(644,495)=1\).

Следовательно, числа 644 и 495 взаимно простые.