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

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

644 = 495 + 149;

495 = 3 · 149 + 48;

149 = 3 · 48 + 5;

48 = 9 · 5 + 3;

5 = 1 · 3 + 2;

3 = 1 · 2 + 1.

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