6. Докажите, что: а) числа 578 и 968 не взаимно простые; б) числа 2781 и 328 взаимно простые.

а) Оба числа чётные: 578 = 2 · 289, 968 = 2 · 484. Следовательно, у них есть общий делитель 2, больший 1, поэтому числа не взаимно простые.

б) Найдём НОД алгоритмом Евклида: 2781 = 8 · 328 + 157; 328 = 2 · 157 + 14; 157 = 11 · 14 + 3; 14 = 4 · 3 + 2; 3 = 1 · 2 + 1. Последний ненулевой остаток равен 1, значит, НОД(2781, 328) = 1. Следовательно, числа взаимно простые.