Таблица 1
Простые числа среди первой тысячи чисел
Некоторые энтузиасты-вычислители уже подготовили таблицы простых чисел, превосходящих 10 000 000. Но, по-видимому, не имеет большого смысла идти на значительные затраты и усилия, чтобы опубликовать эти таблицы. Лишь в очень редких случаях математику, даже специалисту в теории чисел, приходится решать вопрос о том, является ли какое-то большое число простым. Кроме того, большие числа, о которых математик хочет узнать, являются они составными или простыми, не берутся им произвольно. Числа, которые он хочет исследовать, обычно появляются в специальных математических задачах, и, таким образом, эти числа имеют очень специфическую форму.
Система задач 2.1.
1. Какие из следующих чисел являются простыми: а) год вашего рождения; б) текущий год; в) номер вашего дома.
2. Найдите простое число, следующее за простым числом 1973.
3. Заметим, что числа от 90 до 96 включительно являются семью последовательными составными числами; найдите девять последовательных составных чисел.
§ 2. Простые числа Мерсенна
В течение нескольких столетий шла погоня за простыми числами. Многие математики боролись за честь стать открывателем самого большого из известных простых чисел. Разумеется, можно было бы выбрать несколько очень больших чисел, не имеющих таких очевидных делителей, как 2, 3, 5, 7, и проверить, являются ли они простыми числами. Этот способ, как мы вскоре убедимся, не очень эффективен. Теперь эта погоня утихла, она идет только в одном направлении, оказавшемся удачным.
Простые числа Мерсенна являются простыми числами специального вида
Мр = 2p - 1, (2.2.1)
где р — другое простое число. Эти числа вошли в математику давно, они появляются еще в евклидовых размышлениях о совершенных числах, которые мы рассмотрим позже. Свое название они получили в честь французского монаха Мерена Мерсенна (1588–1648), который много занимался проблемой совершенных чисел.
Если начать вычислять числа (2.2.1) для различных простых чисел р, то видно, что не все они оказываются простыми. Например,
М2 = 22 — 1 = 3 = простое,
М3 = 23 — 1 = 7 = простое,
М5 = 25 — 1 = 31 = простое,
М7 = 27 — 1 = 127 = простое,
М11 = 211 — 1 = 2047 = 23 89.
Общий способ нахождения больших простых чисел Мерсенна состоит в проверке всех чисел Мp для различных простых чисел р.
Эти числа очень быстро увеличиваются и столь же быстро увеличиваются затраты труда на их нахождение. То, что с этой работой все-таки можно справиться уже для довольно больших чисел, объясняется существованием эффективных способов выяснения простоты для чисел такого вида.
В исследовании чисел Мерсенна можно выделить раннюю стадию, достигшую своей кульминации в 1750 году, когда Леонард Эйлер[5] установил, что число М31 является простым. К этому времени было найдено восемь простых чисел Мерсенна, соответствующих значениям
р = 2, р = 3, р = 5, р = 7, р = 13, р = 17, p = 19, р = 31.
Эйлерово число M31 оставалось самым большим из известных простых чисел более ста лет. В 1876 году французский математик Лукас установил, что огромное число
М127 = 170141183460469231731687303715884105727
является простым числом. Ну и число! С 39 цифрами. Простые числа Мерсенна, меньшие этого числа, задаются значениями р, указанными выше, а также значениями
р = 61, р = 89, р = 107.
Эти 12 простых чисел Мерсенна были вычислены с помощью только карандаша и бумаги, а для вычисления следующих уже использовались механические настольные счетные машины. Появление вычислительных машин с электрическим приводом позволило продолжить поиски, доведя их до р = 257. Однако результаты были неутешительными, среди них не оказалось новых простых чисел Мерсенна.
Затем задача была переложена на плечи ЭВМ. Создание все более высокопроизводительных ЭВМ дало возможность продолжить поиск новых простых чисел Мерсенна. Д. X. Лемер установил, что значения
р = 521, р = 607, р = 1279, р = 2203, р = 2281
дают простые числа Мерсенна. Дальнейшие поиски также увенчались успехом. Ризель (1958) показал, что
р = 3217,
дает простое число Мерсенна, а Гурвиц (1962) нашёл еще два таких значения:
р = 4253, р = 4423.
Огромного успеха добился Гиллельс (1964), который нашел простые числа Мерсенна, соответствующие значениям