3. Докажите, что числа: а) 26 и 25 не взаимно простые; б) 301 и 5855 взаимно простые.

а) Утверждение в задании ошибочно: числа 26 и 25 взаимно простые. Действительно, \(26=2\cdot13\), а \(25=5^2\), общих простых множителей у них нет, поэтому НОД равен 1.

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

\(5855=301\cdot19+136\);
\(301=136\cdot2+29\);
\(136=29\cdot4+20\);
\(29=20\cdot1+9\);
\(20=9\cdot2+2\);
\(9=2\cdot4+1\).

Последний ненулевой остаток равен 1, значит, числа 301 и 5855 взаимно простые.

Ответ: а) 26 и 25 взаимно простые, поэтому доказать обратное утверждение нельзя; б) 301 и 5855 взаимно простые.