3. Докажите, что числа: а) 260 и 117 не взаимно просты; б) 945 и 544 взаимно просты.

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

260 = 2 · 117 + 26; 117 = 4 · 26 + 13; 26 = 2 · 13.

НОД(260, 117) = 13, поэтому числа не взаимно просты.

б) Найдём НОД:

945 = 544 + 401; 544 = 401 + 143; 401 = 2 · 143 + 115; 143 = 115 + 28; 115 = 4 · 28 + 3; 28 = 9 · 3 + 1.

НОД(945, 544) = 1, поэтому числа взаимно просты.