Теорема (Эйлера). При m > 1 и D(a,m) = 1 имеем
aj(m) º 1 (mod m).
Теорема (малая теорема Ферма). Если p – простое число, то
ap º a (mod p).
Доказательство. Если a кратно p, то, очевидно, ap º 0 º a (mod p). Поэтому достаточно рассмотреть случай, когда a mod p ¹ 0. Так как p – простое число, то отсюда следует, что a взаимно просто с p. Рассмотрим следующие числа:
0 mod p, a mod p, 2a mod p, ..., (p–1)a mod p. (4)
Все эти p чисел различны, так как если бы ax mod p = ay mod p, то в соответствии с определением сравнения, ax º ay (mod p) и, следовательно, на основании свойств сравнений, x º y (mod p), а это невозможно, так как коэффициенты при a есть числа 0, 1, ..., p–1.
Итак последовательность (4) содержит p различных неотрицательных целых чисел, меньших чем p. Первое число – нуль, а остальные суть целые числа 1, 2, ..., p–1, взятые в некотором порядке. Поэтому, на основании свойств сравнений, получим
(a)×(2a)×...×((p–1)a) º 1×2×...×(p–1) (mod p). (5)
Умножая обе части сравнения на a, получаем
ap(1·2·...·(p–1)) º a(1·2·...·(p–1)) (mod p),
что доказывает теорему, так как каждый множитель 1, 2, ..., p–1 взаимно прост с p и может быть сокращен.
Иногда эту теорему приводят в несколько другой формулировке.
Теорема. Если p – простое число, a – целое число, не делящееся на p, то
ap–1 º 1 (mod p).
Такая формулировка сразу следует из (5). В такой формулировке эта теорема является следствием теоремы Эйлера при m = p.
Обсудим применение сравнений в качестве метода определения того, является ли некоторое большое число простым или составным. Этот очень эффективный метод особенно хорош, когда речь идет о некотором числе, выбранном наугад. Он основан на малой теореме Ферма.
Пусть n – исследуемое число. Выберем небольшое число a взаимно простое с n. Удобно в качестве числа a брать некоторое небольшое простое число, не являющееся делителем числа n, например, 2, 3 или 5. Если бы n было простым числом, то для него было бы справедливо сравнение
an–1 º 1 (mod n),
в соответсвие с малой теоремой Ферма. Следовательно, если мы проверим это сравнение и убедимся, что оно не выполняется, то можно утверждать, что число n является составным. К сожалению данный метод метод не указывает на то, какие именно множители имеет данное число. Также к сожалению, данная теорема является необходимым, но не достаточным условием простоты числа, т.е. теорема, обратная малой тереме Ферма в общем случае не верна. Поэтому, если окажется, что последнее сравнение выполняется, то отсюда не следует простота числа. Необходимо исследовать это число с помощью каких-либо других методов.