Восемь этюдов о бесконечности. Математическое приключение - Хаим Шапира

Кстати говоря, доказательство того, что это чудовищное число относится к простым числам, было получено не живым математиком из плоти и крови, а сетевым вычислительным проектом под названием GIMPS (Great Internet Mersenne Prime Search – «Великий интернет-поиск простых чисел Мерсенна»).

Что же такое «число Мерсенна»? Возможно, правильнее было бы спросить иначе: кто такой Мерсенн? Числа вида 2n – 1 называют числами Мерсенна в честь французского философа, богослова, музыковеда и математика Марена Мерсенна (1588–1648). Если вам кажется, что перечень его титулов недостаточно впечатляющ, позвольте мне добавить еще один: Мерсенн был первым человеком, измерившим скорость звука.

Все ли числа Мерсенна простые? Вовсе нет.

Например, 24 – 1 = 15 – не простое число (15 = 3 × 5).

Те, кто еще не забыл уроки старших классов (или, скажем, все еще учится в школе), вероятно, знают, что число Мерсенна не относится к простым, если простым числом не является его степенной показатель. Дело в том, что в этом случае такое число всегда можно разложить на два сомножителя. Механизм, лежащий в основе этого правила, любезно вызвалось проиллюстрировать на собственном примере число 26 – 1:

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

Если эта формула не кажется вам особенно интересной, не беспокойтесь. Собственно говоря, сама формула не столь важна. Важен тот факт, что если в степенном показателе стоит не простое число, то и число Мерсенна с этим показателем не будет простым. Но если составной показатель гарантирует составное число Мерсенна, дальше, несомненно, естественно задать следующий вопрос: «Гарантирует ли простой показатель, что число Мерсенна будет простым?»

Попробуем проверить.

2² – 1, 2³ – 1, 25 – 1 и 27 – 1 – числа простые (соответственно 3, 7, 31 и 127). Пока что все хорошо. Сле- дующее простое число после 7 – это 11, но 211 – 1 – это не простое число: 211 – 1 = 2047 = 23 × 89.

Как ни печально, наличие простого числа в степенном показателе не гарантирует, что соответствующее число Мерсенна тоже будет простым числом. Будь это так, мы бы располагали простым способом находить все новые и новые простые числа. Например, можно было бы взять то колоссальное простое число, о котором мы говорили несколькими строчками выше, использовать его в качестве степенного показателя 2, вычесть единицу и получить новое – и еще более колоссальное – простое число. В его показателе стояло бы число, содержащее более 20 миллионов цифр. Подумайте только, каким ужасающе огромным было бы это число – оно выходило бы за пределы воображения простых смертных. Простое ли это число на самом деле? Я этого не знаю и не думаю, что когда-нибудь узнаю.

Мерсенн исследовал эти числа, носящие теперь его имя, в работе, опубликованной в 1644 г. Она вышла под величественным заголовком «Физико-математические размышления» (Cogitata Physico-Mathematica). Мерсенн проверил все простые степенные показатели до 257 и заключил, что числа вида 2P – 1 должны быть простыми при P = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257. Правильный перечень немного отличается от этого и выглядит так: P = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127.

Судите сами, можно ли считать процент точных попаданий Мерсенна впечатляющим.

Числа Мерсенна и совершенные числа

Помните совершенные числа, с которыми мы познакомились в разделе, посвященном Пифагору? Если вы уже забыли про них, напомню, что совершенным называется число, сумма собственных делителей которого равна самому числу. Еще Евклид знал, что, если 2P – 1 – простое число, то его умножение на 2P – 1 всегда дает совершенное число. Разумеется, Евклид не называл такие числа числами Мерсенна. В его время не только еще не родился сам Мерсенн, но даже не познакомились родители прародителей его прародителей.

Приведем несколько примеров. 2³ – 1 – простое число (7); следовательно, (2³ – 1) × 2² = 28 – число совершенное. Аналогичным образом, 25 – 1 – простое число (31); следовательно, (25 – 1) × 24 = 496 – число совершенное. Воспользовавшись любезной помощью наибольшего из известных на сегодня простых чисел, мы теперь можем построить и самое большое из известных совершенных чисел: (277 232 917 – 1) × 277 232 916.

Я не советовал бы вам пытаться сосчитать это число и проверить справедливость этого утверждения. Могу вас заверить, что сумма всех делителей этого чудовищного числа действительно равна самому числу. Говоря словами великого немецкого философа Иммануила Канта, мне пришлось устранить знание, чтобы дать место вере.

Ну хорошо. Теперь настало время отвлечься от мировых рекордов и заняться разработкой некоторых из пресловутых умственных мускулов.

Головоломки для тех, кто изучал математику

1). Докажите, что, если 2P – 1 – простое число, то число (2P – 1) × 2P – 1 должно быть совершенным.

2). 28 – треугольное число.

Являются ли все совершенные четные числа треугольными?

Знаменитый швейцарский математик Леонард Эйлер (с которым мы вскоре познакомимся) доказал, что верно и обратное. Другими словами, любое четное совершенное число имеет форму (2P – 1) × 2P – 1, где P и 2P – 1 – простые числа. Попробуйте свои силы и докажите это утверждение – или же найдите доказательство Эйлера{14}.

Ну ладно, мы поняли, что простых чисел существует бесконечное количество. После этого логично было спросить, есть ли в их появлении какой-либо порядок. Существует ли формула, дающая только простые числа? Существует ли формула, дающая все простые числа? Как могла бы выглядеть формула количества простых чисел до некоторого числа n?