Теорема 1. Если p- простое число и a− целое число, не делящееся на p, то a p−1−1 делится на p, т.е.
| a p−1≡1 (mod p). | (1) |
Для доказательства теоремы 1 потребуется следующая лемма.
Лемма. Для любого простого числа p и целого числа k не кратного p, произведение k и чисел 1, 2, 3, ..., p−1:
k·1, k·2, k·3, ..., k·(p−1)
при делении на p в остатке дают те же самые числа 1, 2, 3, ..., p−1, возможно записанные в некотором другом порядке.
Доказательство леммы. Произведение числа k с любым из чисел 1, 2, 3, ..., p−1 не делится на p. Следовательно, при делении k·1, k·2, k·3, ..., k·(p−1) на p не может быть нулевой остаток.
Докажем, что все остатки разные. Предположим, обратное. Пусть произведения ka и kb при делении на p дают одинаковые остатки, тогда ka−kb=k(a−b) делится на p. Но это невозможно, поскольку a−b не делится на p (т.к. |a−b|< p) . Значит все остатки разные. Существуют всего p−1 различных ненулевых остатков от деления на p и все они меньше p. Лемма доказана.
Доказательство теоремы 1. Согласно доказанной выше лемме, остатки от деления чисел a, 2a, 3a, ..., (p−1)a совпадают с числами 1,2,3, ..., p−1 с точностью до перестановки. Тогда
a·2a·3a ... (p−1)a ≡ 1·2·3 ... (p−1) (mod p).
Отсюда
| a p−1(p−1)! ≡ (p−1)! (mod p). | (2) |
Из выражения (2) следует, что
| a p−1(p−1)! − (p−1)! = (a p−1−1)(p−1)! | (3) |
делится на p. Так как все сомножители 1, 2, 3, ..., p−1 выражения (p−1)! взаимно простые с p, то a p−1−1 делится на p или можно записать:
| a p−1 ≡ 1 (mod p). |
Теорема доказана.
Альтернативная формулировка малой теоремы Ферма отличается тем, что не требует, чтобы a не делилось на p.
Теорема 2. Если p - простое число, то для каждого целого числа a
| a p≡a (mod p). | (4) |
Иными словами, если p - простое число, то для каждого целого числа a, a p−a делиться на p.
Доказательство теоремы. Если a делится на p, то a p−a=a(a p−1−1) делится на p. Выражение (4) эквивалентна выражению a·a p−1 ≡ 1·a (mod p). Если же a не делится на p, то наибольший общий делитель чисел a и p равно 1. Тогда по утверждению 5 статьи "Сравнение чисел по модулю" выражение a·a p−1 ≡ 1·a (mod p) эквивалента выражению a p−1 ≡ 1 (mod p).