Малая теорема Ферма

Теорема 1. Если p- простое число и a− целое число, не делящееся на p, то a p−1−1 делится на p, т.е.

a p−11 (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 pa (mod p). (4)

Иными словами, если p - простое число, то для каждого целого числа a, a pa делиться на p.

Доказательство теоремы. Если a делится на p, то a pa=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).