Глава 11. Тесты на простоту и примитивные корни

В этой главе мы доказываем знаменитую теорему Гаусса о цикличности группы при простом Она вдохновляет нас на создание теста, который, в отличие от тестов главы 7, проверяет простоту данного числа. Именно с этого теста мы и начинаем главу.

§ 11.1. Тест Люка

Предположим, что мы хотим определить, является ли данное нечетное число простым. Один из возможных путей — попытаться показать, что порядок группы равен т.е. имеет место равенство: Бели это так, то любое натуральное число а, меньшее должно быть взаимно простым с ним, что возможно только для простого На первый взгляд задача кажется безнадежной. Как пересчитать элементы в если очень большое? Свет в конце туннеля забрезжит после осознания следующей теоремы, которая доказывается в § 11.5.

Теорема о примитивных корнях. Если простое число, то циклическая группа.

Как следует из теоремы, в случае простого в группе найдется элемент 6 порядка Говоря языком формул,

Это наводит на мысль о следующей стратегии. Предположим, что для натурального числа нам как-нибудь удалось найти элемент порядка По теореме Лагранжа порядок элемента 6 должен делить порядок группы т.е. делит Однако так что Значит, простое число. Согласно теореме о примитивных корнях такой элемент всегда найдется, если простое число. Теорема, естественно, не утверждает, что этот элемент будет легко отыскать; чтобы его обнаружить, мы должны быть в хороших отношениях с удачей.

Применение нашей стратегии к тестированию простоты конкретного числа требует несложного способа проверки факта: данный элемент группы имеет порядок Такой способ указывает нам сформулированный ниже тест, предложенный Лемером в 1927 году. Он основывается на чуть более слабом тесте, авторство которого принадлежит Люка.

Тест Люка. Пусть нечетное натуральное и целое число, подчиняющееся неравенству Если для каждого простого делителя числа справедливы следующие утверждения:

то - простое число.

Доказательство. Обозначим через к порядок элемента b группы Нам хотелось бы показать, что По условию, поэтому ключевая лемма гарантирует

делимость на для некоторого натурального Достаточно доказать, что

Допустим, это не так, т.е. Тогда делится на какое-то простое число Но если делит то делит и иначе говоря, и целые числа. Более того, из равенства

мы заключаем, что к делит Очередное применение ключевой леммы дает: что противоречит предположениям теста. Следовательно, Теперь, по теореме Лагранжа, порядок элемента должен делить порядок группы равный Таким образом, простое число.

Прежние тесты могли установить только разложимость того или иного числа. А тест Люка определяет его простоту. Заметим, что для успешного применения теста Люка нам нужно знать полное разложение числа на множители. К счастью, такое разложение во многих случаях легко получить для целых семейств чисел; например, для чисел Ферма и их делителей. Нам должно только повезти с выбором кандидата в противном случае тест выдаст неопределенный ответ, даже если число простое.

Опираясь на тест Люка, докажем тест на простоту для чисел Ферма, впервые предложенный Жаном Франсуа Теофилом Пепэном (Jean Frangois Theophile Pepin) (1826-1904).

Тест Пепэна. Число Ферма является простым при данном если и только если

Предположим сначала, что сравнение из формулировки теста выполнено. Заметим, что единственным простым

делителем числа является 2. Поскольку

в то время как

из теста Люка вытекает, что простое число. В обратную сторону тест доказывается труднее, с использованием квадратичного закона взаимности. Мы не будем приводить здесь этого доказательства. Заинтересованный читатель может посмотреть полное доказательство теста в [23].

Опробуем тест Пепэна на доказательстве простоты числа Имеет место равенство

но

Итак, условия теста выполнены и простое число. Тест Пепэна легок в применении, поскольку он требует вычисления только квадратов по модулю а это можно сделать довольно быстро.

В качестве второго примера докажем, что число из повторяющихся единиц

простое. Прежде чем применять тест Люка, найдем полное разложение числа на множители:

Сначала в качестве выберем 2. С помощью любой программы символьных вычислений легко показать, что

Но, к сожалению,

Значит, условие (2) теста Люка не выполняется для и мы ошиблись в выборе кандидата.

Затем положим Применив программу символьных вычислений, найдем

Таким образом, число 3 удовлетворяет условию (1) теста, и нам нужно найти вычеты степеней

по модулю для каждого из простых делителей, участвующих в разложении числа Сделаем это с помощью компьютера и сведем результаты в таблицу:

(см. скан)

Из таблицы видно, что условие (2) теста Люка выполняется для каждого простого делителя числа Следовательно, действительно простое число.

Среди чисел, в записи которых участвуют только единицы известно всего лишь 5 простых. Первое, естественно, второе из них; остальные — это Доказать простоту числа несложно, если при этом руководствоваться усовершенствованным тестом Люка, который мы описываем в следующем параграфе (см. упражнение 4).