Найдите все ошибки в «доказательстве». «Теорема». Если целое число а взаимно просто с натуральным числом n, то aⁿ⁻¹ — 1 делится на n. «Доказательство». Рассмотрим числа 1·a, 2·a, 3·a, ..., (n-1)·a. Допустим, какие-то два из них имеют одинаковые остатки при делении на n, то есть ai ≡ aj (mod n), откуда a(i-j) делится на n. Следовательно, (i-j) делится на n, но тогда i=j, противоречие. Перемножив все числа, получим сравнение 1·2·...·(n-1) ≡ aⁿ⁻¹·1·2·...·(n-1) (mod n). Сократив на (n-1)!, получим сравнение aⁿ⁻¹ ≡ 1 (mod n).

Краткое пояснение

Пошаговое решение:

1. Ошибка 1: Условие сокращения.

   Утверждение, что \( (i-j) \) делится на \( n \), является следствием \( a(i-j) \) делится на \( n \) и \( a \) взаимно просто с \( n \). Однако, для того чтобы сократить обе части сравнения \( 1 · 2 · … · (n-1) ≡ a^{n-1} · 1 · 2 · … · (n-1) \) на \( (n-1)! \), необходимо, чтобы \( (n-1)! \) было взаимно просто с \( n \). Это условие не всегда выполняется.

2. Ошибка 2: Некорректное следствие из делимости.

   Из того, что \( a(i-j) \) делится на \( n \) и \( a \) взаимно просто с \( n \), следует, что \( i-j \) делится на \( n \). Это верно. Однако, в контексте остатков при делении на \( n \) для чисел \( 1, 2, …, n-1 \), если \( i ≠ j \), то \( i-j \) будет находиться в диапазоне от \( -(n-2) \) до \( n-2 \). Единственное кратное \( n \), которое может попасть в этот диапазон, это \( 0 \). Следовательно, \( i-j=0 \), что означает \( i=j \). Таким образом, если \( i ≠ j \), то остатки не могут быть одинаковыми.

   Более точная формулировка теоремы Ферма: Если \( p \) — простое число, то для любого целого числа \( a \), не делящегося на \( p \), выполняется сравнение \( a^{p-1} ≡ 1 · \) (mod \( p \)).

Итоговая поправка: Корректное доказательство часто использует тот факт, что числа \( 1 · a, 2 · a, …, (n-1) · a \) дают в остатке при делении на \( n \) числа \( 1, 2, …, n-1 \) в некотором порядке, если \( n \) — простое число.