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

Найдём НОД чисел алгоритмом Евклида:

195 = 76 · 2 + 43;

76 = 43 · 1 + 33;

43 = 33 · 1 + 10;

33 = 10 · 3 + 3;

10 = 3 · 3 + 1.

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

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