Еще раз о теореме Ферма.

Малая теорема Ферма играет важную роль в цифровом кодировании, и мы рассмотрим ее более подробно. Бели для некоторого числа а число — а (полученное из ) дает ненулевой остаток при делении на то, то — составное число. Предположим, напротив, что — а делится на то. Следует ли из этого, что — простое число? Отдельные примеры наводят на мысль, что да: делится на делится на делится на делится на 7, и числа 2, 3, 5, 7 простые.

У древних китайцев был следующий тест простоты: число то является простым тогда и только тогда, когда то делит , или . Эта теорема не обсуждалась в течение многих столетий, и Лейбниц верил, что она верна. На самом деле верна лишь вторая часть — «только тогда», а первая часть неверна, как продемонстрировал в 1819 г. французский математик Пьер Фредерик Сарю. Он показал, что 2341 — 2 делится на 341, в то время как 341 — составное число, произведение 11 на 13. Это нетрудно проверить, если воспользоваться сравнением

откуда вытекает, что

После открытия Сарю было найдено много других контрпримеров с различными значениями основания а; например,

делится на составное число 91, и так далее. Конечно, не всегда проверка будет такой простой, как в случае вычисления когда мы воспользовались тем, что Поэтому в общем случае придется возводить число в степень, но мы уже знаем аффективный метод для этого.

Составные числа, которые ведут себя так, как простые в теореме Ферма для данного основания а, называются псевдопростыми по основанию а. Число 341 является наименьшим псевдопростым по основанию 2, а число 91 — наименьшим псевдопростым по основанию 3. Оказывается, что для всякого основания а существует бесконечно много псевдопростых чисел (см. теорему 2.3.28). Существуют даже составные числа, такие, как которые являются псевдопростыми по любому основанию а. Числа такого вида, называемые кармайкловыми, будут рассмотрены ниже (см. историческое замечание 5).

По контрасту со сказанным выше следующая теорема справедлива тогда и только тогда, когда — простое число.

Теорема 2.3.16 (Вильсон), тогда и только тогда, когда — простое число.

Доказательство. Для доказательства, не использующего теорию групп, в случае простого рассмотрим произведение . Здесь все сомножители имеют различные мультипликативные обратные по модулю (см. также упр. этому разделу); например, для рассмотрим , где числа 2 и 4, а также 3 и 5 образуют пары взаимно обратных по модулю 7. Произведение элементов такой пары и то же самое выполняется для произведения всех таких пар. Другими словами,

домножая его , получим

Рассмотрим функцию . Из теоремы Вильсона получаем, что принимает нулевое значение тогда 1 только тогда, когда — простое число. К сожалению, теорема

Вильсона в качестве теста простоты не имеет никакой практической ценности, потому что приходится вычислять очень большое число даже для небольших значений .