Алекс в стране чисел. Необычайное путешествие в волшебный мир математики - Алекс Беллос

В своих «Началах» Евклид показал, что всегда, когда сумма удвоений есть простое число, можно найти совершенное число, умножая сумму на наибольшее из тех удвоений, что в нее входят. Это звучит как малопонятная тирада, так что давайте начнем складывать удвоения, чтобы увидеть, что же все это означает.

Доказательство Евклида было, конечно, геометрическим. Он не записывал его в терминах чисел, а использовал отрезки прямых. Однако если бы он мог позволить себе роскошь современных алгебраических обозначений, то заметил бы, что сумму удвоений 1 + 2 + 4 +… можно выразить как сумму степеней двойки, 20 + 21 + 22 +… (Заметим, что любое число в степени 0 есть 1 и что любое число в степени 1 есть само это число.) Тогда становится понятным, что любая сумма удвоений равна следующему удвоению за вычетом единицы. Например:

Это можно обобщить в виде формулы 20 + 21 + 22 +… + 2n-1 = 2n - 1. Другими словами, сумма первых n удвоений равна 2n - 1.

Итак, используя исходное заявление Евклида о том, что «когда сумма удвоений есть простое число, можно построить совершенное число, умножая сумму на наибольшее из тех удвоений, что в нее входят» и добавляя к этому современные алгебраические обозначения, мы можем получить намного более четкое утверждение:

Для цивилизаций, которые превозносили совершенные числа, данное Евклидом доказательство было потрясающей новостью. Если совершенные числа можно породить всякий раз, когда число 2n - 1 простое, то все, что нужно для нахождения новых совершенных чисел, — это нахождение простых чисел, которые можно записать в виде 2n - 1. Охота за совершенными числами свелась к охоте за простыми числами определенного типа.

Конечно, математический интерес к простым числам, записываемым в виде 2n - 1, мог быть связан с совершенными числами, однако к XVII столетию простые числа стали объектом увлечения сами по себе. В то время как одни математики были поглощены вычислением числа π со все большим и большим количеством десятичных знаков, другие посвящали себя нахождению все больших и больших простых чисел. Эти два рода деятельности похожи, но противоположны: если вычисление десятичных знаков в числе π — это поиск все меньших и меньших объектов, то погоня за простыми числами — это взлет вверх, в небеса. Развитию обоих направлений способствовала скорее романтическая аура самого путешествия, нежели возможности практического использования чисел, открытых по дороге.

В ходе этого поиска простые числа вида 2n - 1 зажили своей собственной жизнью. Эта формула не давала простых чисел при всех значениях n, но для малых чисел процент успеха был весьма неплох. Как мы уже видели, при n = 2, 3, 57 число 2n - 1 — простое.

Французский монах (и одновременно один из выдающихся ученых своего времени) Марен Мерсенн (1588–1648) просто зациклился на использовании чисел вида 2n - 1 для производства простых. В 1644 году он выступил с широкомасштабным заявлением о том, что ему известны все значения n до 257, при которых число 2n - 1 простое. По его словам, это были значения

Мерсенн был дельным математиком, однако его список — по большей части плод угадывания. Число 2257 - 1 состоит из 78 цифр — определенно слишком много для проверки человеческими силами на предмет того, простое оно или нет. Мерсенн осознавал, что его числа — это стрельба наугад. Он говорил о своем списке: «Всего времени не хватит, дабы определить, простые ли они».

Но одному математику времени тем не менее все-таки хватило, — такое нередко бывает в науке. В 1876 году, через два с половиной столетия после того, как Мерсенн предложил свой список, французский специалист по теории чисел Эдуар Люка изобрел метод, позволяющий проверить, являются ли числа вида 2n - 1 простыми, и выяснил, что Мерсенн был не прав по поводу числа 67 и, кроме того, он пропустил числа 61, 89 и 107. Потрясающе, однако, что Мерсенн оказался прав насчет числа 127. Люка применил свой метод для доказательства того, что число 2127 - 1 (то есть 170 141 183 460 4 69 231 731 687 303 715 884 105 727) — простое. Оно оставалось самым большим известным простым числом до наступления века компьютеров. Люка, однако, не смог определить, простое или нет число 2257 - 1 — оно было слишком большим для ручных вычислений.

Несмотря на отдельные ошибки, список Мерсенна обессмертил своего создателя; простые числа вида 2n - 1 в наше время известны как простые числа Мерсенна.

* * *

Дабы выяснить, простое или нет число 2257 - 1, пришлось дожидаться наступления 1952 года. Для доказательства был использован метод Люка, правда при существенной поддержке. В том году в Институте численного анализа в Лос-Анджелесе собралась команда ученых. Они наблюдали за 24-футовыми барабанами с магнитной лентой, вводившейся в один из первых цифровых компьютеров, который назывался SWAC. Один только этот процесс занял несколько минут. Затем оператор ввел число, которое предстояло проверить: 257. Через долю секунды появился результат. Компьютер сообщил, что число 2257 - 1 — не простое.

Вечером того же дня, когда было получено, что число 2257 - 1 — не простое, в вычислительную машину один за другим были введены новые претенденты на право занять место в списке Мерсенна. SWAC отказал первым 42 из них. И только в 10 вечера появился результат: компьютер сообщил, что число 2521 - 1 — простое. Это число было наибольшим из простых чисел Мерсенна, выявленным за 75 лет, что, кстати, давало и соответствующее совершенное число 2520(2521 - 1) — всего лишь тринадцатое открытое за чуть ли не вдвое большее число столетий. Но число 2521 - 1 только два часа наслаждалось своим статусом старшего в колоде. Незадолго до полуночи SWAC подтвердил, что число 2607 - 1 тоже простое. За последующие несколько месяцев SWAC, работая на пределе своих возможностей, нашел еще три простых числа. 17 простых чисел Мерсенна были открыты в период с 1957 по 1996 год.