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

Найдём наибольший общий делитель алгоритмом Евклида:

644 = 495 · 1 + 149;

495 = 149 · 3 + 48;

149 = 48 · 3 + 5;

48 = 5 · 9 + 3;

5 = 3 · 1 + 2;

3 = 2 · 1 + 1.

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

Ответ: числа 644 и 495 взаимно простые.