№ 149. Докажите, что: 1) числа 945 и 572 — взаимно простые; 2) числа 1095 и 738 — не взаимно простые.

1. Найдём НОД алгоритмом Евклида:

   945 = 572 · 1 + 373;

   572 = 373 · 1 + 199;

   373 = 199 · 1 + 174;

   199 = 174 · 1 + 25;

   174 = 25 · 6 + 24;

   25 = 24 · 1 + 1;

   24 = 1 · 24.

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

2. 1095 = 738 · 1 + 357;

   738 = 357 · 2 + 24;

   357 = 24 · 14 + 21;

   24 = 21 · 1 + 3;

   21 = 3 · 7.

   Последний ненулевой остаток равен 3, значит, НОД(1095, 738) = 3. Следовательно, числа имеют общий делитель, больший 1, и не являются взаимно простыми.

Ответ: 945 и 572 взаимно простые; 1095 и 738 не взаимно простые.