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

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

\(644 = 495 + 149\);
\(495 = 3 \cdot 149 + 48\);
\(149 = 3 \cdot 48 + 5\);
\(48 = 9 \cdot 5 + 3\);
\(5 = 1 \cdot 3 + 2\);
\(3 = 1 \cdot 2 + 1\).

Последний ненулевой остаток равен 1, значит, \(\mathrm{НОД}(644,495)=1\). Следовательно, числа 644 и 495 взаимно простые.