Глава 10. Мерсенн и Ферма

В первых двух параграфах этой главы мы изучаем классические методы, применяемые для поиска делителей чисел Мерсенна и Ферма. Однако вместо того, чтобы следовать оригинальному подходу Ферма и Эйлера, здесь используется язык теории групп и результаты, полученные в главе 9. Такой подход позволит нам разобраться с делителями упомянутых чисел пррстым и изящным способом. Теми же методами в § 10.4 доказывается очень эффективный тест на простоту для чисел Мерсенна.

§ 10.1. Числа Мерсенна

Один из лучших способов генерирования очень больших простых чисел использует экспоненциальные формулы. Старейшая экспоненциальная формула для простых чисел названа по имени Мерсенна. Пусть натуральное число. Напомним, что числом Мерсенна называется

Мы уже видели, что число составное, если таковым

является Для имеем

Следовательно, делитель числа Естественно, тоже делит

Таким образом, при поиске простых чисел Мерсенна мы можем ограничиться исследованием с простыми Однако утверждение о простоте всех таких не верно. В этом параграфе описывается метод разложения на множители чисел Мерсенна с простым, но не слишком большим показателем. Главную движущую пружину метода дает общая формула делителей числа открытая Ферма. Для доказательства формулы нам потребуется еще один результат из теории групп.

Ключевая лемма. Пусть конечная группа с операцией и Натуральное число удовлетворяет условию тогда и только тогда, когда делится на порядок элемента а.

Доказательство. Обозначим через s порядок элемента а. Делимость на s означает равенство: при некотором натуральном . В этом случае

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

Отсюда

(по условию, Но ввиду неравенства и выбора s последнее соотношение возможно, только если

Вернемся к числам Мерсенна. Предположим, что простой делитель числа соответствующего простому Тогда

Это сравнение можно интерпретировать как равенство в группе а именно:

Что можно сказать о порядке элемента 2 группы Из предыдущего соотношения и ключевой леммы вытекает, что он делит Но простое число, значит, порядком элемента 2 может быть только либо 1, либо Предположение о том, что приводит к противоречию: (ввиду равенства . Следовательно, элемент 2 имеет порядок в группе . С другой стороны, по теореме Ферма

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

Полученное соотношение можно усилить. Действительно, число нечетное, так что все его делители тоже нечетны. В частности, разность четна. Далее, из нечетности вытекает, что число к в разложении на множители должно быть четным. Следовательно, для некоторого натурального числа Мы доказали следующий результат.

Метод Ферма. Пусть простое число, простой делитель числа Мерсенна Тогда найдется такое натуральное что

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

числа имеет вид: Теперь нам предстоит вычислить при и выбрать из полученных результатов делители числа Перед началом вычислений полезно подумать, как далеко нам следует заходить в этом процессе. Напомним (см. § 3.2), что если наименьший простой делитель составного числа то

А так как из последнего неравенства вытекает, что

При это ограничение оставляет нам только два возможных значения для и 2. Подстановка в формулу дает Элементарное деление показывает, что 23 действительно является множителем числа Другой его простой делитель — это Любопытно отметить, что если бы мы искали делители числа методом проб, как в § 3.2, то нам пришлось бы безуспешно делить на каждое простое число, меньшее 23. А таких чисел 8.

История чисел Мерсенна — кладезь курьезов и анекдотических случаев. Один из лучших — доклад Коула на заседании Американского Математического Общества в 1903 году. Он доказал, что

перемножая эти числа в полной тишине. Аудитория с энтузиазмом приняла доказательство! Простым способом получить такое разложение пока никто не смог.

Как мы упоминали в главе 3, многие из известных больших простых чисел — числа Мерсенна. Конечно, есть способы проверки чисел Мерсенна на простоту более хорошие, чем метод Ферма. Наиболее часто употребляемый из них — тест Люка-Лемера, который мы объясним в § 10.4.