Как же доказать данное утверждение? Показать, что n^560 - 1 делится на 561 для каждого натурального n, не делящегося на 561.

Предыдущий
вопрос Следующий
вопрос

Для доказательства данного утверждения воспользуемся малой теоремой Ферма: если p - простое число, а a - целое число, не делящееся на p, то a^(p-1) ≡ 1 (mod p).

Так как 561 = 3 11 17, то 561 имеет три различных простых множителя.

Таким образом, мы можем записать:
n^560 ≡ 1 (mod 3),
n^560 ≡ 1 (mod 11),
n^560 ≡ 1 (mod 17).

Так как n не делится на 3, 11 и 17, то n взаимно просто с 3, 11 и 17.

Применим малую теорему Ферма для каждого из простых чисел:
n^2 ≡ 1 (mod 3) => n^560 ≡ (n^2)^280 ≡ 1^280 ≡ 1 (mod 3),
n^10 ≡ 1 (mod 11) => n^560 ≡ (n^10)^56 ≡ 1^56 ≡ 1 (mod 11),
n^16 ≡ 1 (mod 17) => n^560 ≡ (n^16)^35 ≡ 1^35 ≡ 1 (mod 17).

Таким образом, мы доказали, что n^560 ≡ 1 (mod 3), n^560 ≡ 1 (mod 11) и n^560 ≡ 1 (mod 17) для любого натурального числа n, не делящегося на 3, 11 и 17.

Следовательно, n^560 - 1 делится на 3, 11 и 17, а значит, делится и на 561. Таким образом, мы доказали данное утверждение.