§ 10.4. Тест Люка — Лемера

В этом параграфе мы представляем очень хороший тест, проверяющий на простоту числа Мерсенна. Первым его обнаружил Люка (известный нам как создатель «Ханойских башен») в 1878 году. Затем тест был усовершенствован Лемером (D. Н. Lehmer) в 1932 году, и теперь он называется тестом Люка — Лемера.

Главная составная часть представляемого теста — последовательность натуральных чисел: определяемая рекуррентной формулой

Сначала мы покажем, что члены последовательности можно записать в виде сумм степеней некоторых иррациональных чисел (см. упражнение 4 главы 6). Пусть Докажем индукцией по что

Очевидно, Предположим, что Возводя в квадрат обе части равенства, получаем

Поскольку отсюда следует соотношение

что, по определению, дает

Тест Люка — Лемера. Пусть простое число. Число Мерсенна является простым тогда и только тогда, когда

Мы докажем только необходимость условия теста, доказательство достаточности выходит за рамки данной книги. Приводимое здесь доказательство опубликовано в [9]. Будучи элементарным по сути, оно оперирует иррациональными числами таким способом, который трудно обосновать. Но если смириться с иррациональными числами, то в остальном проблем не будет, поскольку доказательство близко следует схеме рассуждений из предыдущих параграфов. Чтобы понять, откуда появляются иррациональные числа, можно обратиться к [8].

Доказательство теста Люка — Лемера излагается на языке теории групп, но группы, используемые при этом, несколько более экзотичны, чем Отправная точка рассуждений — некое подмножество в совокупности чисел вида а где Эти числа можно складывать и умножать как вещественные. При этом сумма и произведение двух элементов из остается в данном множестве. Более того, подобно совокупность являясь группой относительно сложения, не будет таковой относительно умножения. Все упомянутые факты легко проверить. Заметим, что каждое число о можно записать в виде так что

Пусть теперь простое натуральное число. Введем обозначение

Ясно, что Из равенства вытекает, что сумма любых двух чисел из также принадлежит Более того, для любого а как так и лежат в Таким образом, подгруппа в аддитивной (по сложению) группе

Как показано в § 9.8, отношение сравнения по модулю является отношением эквивалентности на множестве Напомним, что если то когда (см. упражнения 10 и 11 главы 5).

Далее элемент записывается в виде где Разделив на с остатком, мы получим причем Обозначив сумму через можно записать

Значит, Число называется приведенной формой элемента а по модулю Поскольку остаток от деления целых чисел определен однозначно, каждый элемент из имеет только одну приведенную форму по модулю Отметим, что в существует ровно различных приведенных форм элементов по модулю

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

Определим умножение в по правилу

Доказательство независимости результата умножения от выбора представителей классов аналогично соответствующей проверке для арифметики остатков (см. § 5.3). Если то простое вычисление показывает, что представитель произведения имеет вид:

Легко проверить, что умножение ассоциативно, коммутативно и имеет 1 в качестве единичного элемента. Однако не является группой по умножению (см. упражнение 9). Как и в случае арифметики остатков, мы преодолеваем эту трудность, вводя множество обратимых по умножению элементов из Оно образует группу, поскольку произведение обратимых элементов множества тоже обратимо, что легко проверяется (см. § 9.4). Ввиду включения

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

Доказательство корректности теста Люка — Лемера. Допустим, что при некотором простом число Мерсенна делит член последовательности Благодаря соотношению (4.1), найдется такое натуральное что

Умножая это равенство на и используя тождество получаем

Допустим теперь, что число составное и пусть его наименьший простой множитель. Приведем наше допущение к противоречию. Поскольку делит из (4.2) следует,

что

Возводя в квадрат равенство (4.3), имеем

Отсюда, руководствуясь ключевой леммой, делаем вывод: порядок элемента делит С другой стороны, уравнение (4.3) говорит нам, что он не может быть степенью двойки, меньшей, чем Итак, порядок элемента в группе равен Далее, по теореме Лагранжа, порядок элемента делит порядок группы а из-за того, что последний не превосходит получаем неравенство Вспоминая теперь, что наименьший простой делитель числа Мерсенна можно оценить сверху: Таким образом,

что противоречит здравому смыслу. Итак, если делит член последовательности то число простое, т.е. мы доказали необходимость условия теста. Доказательство достаточности смотри в [8].

Несмотря на трудности, связанные с доказательством корректности теста, его очень легко реализовать и применить. В 1978 году два старшеклассника Лора Никель (Nickel) и Курт Нолль (Noll) с помощью теста Люка-Лемера доказали простоту числа воспользовавшись локальной компьютерной сетью местного университета. Их успех был отражен в передовице Нью-Йорк Тайме. Этот же тест лежит в основе GIMPS, пакета программ «Great Internet Mersenne Prime Search» - свободно распространяемой (вместе с текстами программ) программной системой. Так что любой владелец персонального компьютера может заняться поиском больших

простых чисел. Наибольшее из известных простых чисел Мерсенна, состоящее из 909526 знаков, это Оно было открыто при помощи GIMPS в январе 1998 года.

Упражнения

(см. скан)

(см. скан)

(см. скан)