Главная > Математика > Введение в теорию чисел. Алгоритм RSA
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 4.2. Экспоненциальные формулы: числа Мерсенна

Есть две экспоненциальные формулы огромной исторической важности. Обе изучались математиками XVII и XVIII веков, в особенности Ферма и Эйлером. Вот эти формулы:

где натуральное. Числа из первой формулы называются числами Мерсенна, а из второй — числами Ферма.

Вопрос о том, при каких значениях числа Мерсенна просты, восходит к математикам античной Греции. В пифагорейском мистицизме число называлось совершенным, если оно

равняется полусумме своих положительных делителей. Например, делители числа 6 - это 1, 2, 3 и 6. Складывая их, получаем:

Следовательно, 6 — совершенное число. Конечно, никакое простое число не будет совершенным. Действительно, делители простого числа это поскольку

Эвклид знал, что число совершенно, если простое. Нетрудно показать, что все четные совершенные числа имеют такой вид, но доказан этот факт был только Эйлером в восемнадцатом веке. Доказательство упомянутых результатов можно найти в упражнениях 8, 9 и 10 главы 3. Формула Эвклида сводит задачу о поиске четных совершенных чисел к нахождению простых чисел Мерсенна.

Задача о нахождении совершенных чисел, имеющая своим истоком туманный мистицизм пифагорейцев, может показаться крайне странной некоторым, живущим в конце двадцатого века. Однако, факт остается фактом: несмотря на то, что проблема стоит около 2500 лет, у нее все еще нет удовлетворительного решения. Например, неизвестно, обязано ли совершенное число быть четным, хотя к настоящему времени не найдено ни одного нечетного. Конечно, возраст этой проблемы бросает труднопреодолимый вызов всем, кто любит числа. Более того, ее сложность может означать, что она относится к глубочайшим свойствам целых чисел. Это делает ее даже еще более важной с точки зрения математиков.

Как мы упоминали во введении, Марэн Мерсенн был священником и математиком-любителем семнадцатого века. Числа вида обязаны своим именем утверждению Мерсенна о том, что они просты, в случае

и являются составными для всех остальных 44 положительных простых меньших 257.

Первое важное замечание: Мерсенн рассматривал значения функции только при простых Действительно, если составное, то такое же и Предположим, что тогда

Следовательно, если делит то делит Второй важный момент заключается в том, что обратное неверно. Иначе говоря, если простое, то не обязано быть простым. Мы видим из списка Мерсенна, что должно быть составным. Это легко проверить:

Как часто бывало в то время, Мерсенн не привел доказательства своего утверждения, что дало повод для сомнений в его истинности и оставило широкое поле деятельности для математиков. В поисках простых чисел Мерсенна принял участие и Эйлер. В 1732 году он нашел два «новых простых» числа: отсутствовавших в списке Мерсенна. Позже выяснилось, что в этом случае Эйлер был не прав. Первую ошибку в списке Мерсенна нашли Первузэн (Pervusin) и Зилхоф (Seelhov) в 1886. Они обнаружили, что число простое, хотя его и нет в списке. Другие ошибки были найдены в последующие годы. Сейчас известно, что кроме в списке пропущены простые числа и присутствуют составные числа

При доказательстве простоты чисел Мерсенна, Ферма использовал метод разложения на множители, который будет описан в § 10.1. В наше время используется гораздо более эффективный тест Люка-Лемера, изучаемый в § 10.4. С помощью этого теста в 1998 году было показано, что число Мерсенна просто. Оно состоит из знаков и является наибольшим из простых чисел, известных к моменту издания этой книги.

<< Предыдущий параграф Следующий параграф >>
Оглавление