Число, пришедшее с холода. Когда математика становится приключением - Рудольф Ташнер

то есть простые числа. Вычитание единицы из представленной составным числом степени числа 2 ни в коем случае не может дать в результате простое число, как это видно из следующих примеров:

24 — 1 = 15 = (2² — 1) × (1 + 22) = 3 × 5,

26 — 1 = 63 = (2³ — 1) × (1 + 2³) = 7 × 9,

28 — 1 = 255 = (24 — 1) × (1 + 24) = 15 × 17,

29 — 1 = 511 = (2³ — 1) × (1 + 2³ + 26) = 7 × 73.

Мерсенн, однако, сам выяснил, что его рецепт действует не всегда, а точнее, весьма редко. Собственно, даже если показатель степени двойки выражен простым числом, разность между степенью и единицей не обязательно является простым числом. Хотя правило Мерсенна работает для показателей степени 2, 3, 5 и 7, сбой происходит уже при показателе, равном 11, ибо 211–1 = 2047, то есть произведению 23 и 89.

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

213 — 1 = 8191, 217 –1 = 131 071 и 219 — 1 = 524 287

являются простыми. Мерсенн утверждал, что то же самое верно и для показателей степени 31, 67, 127 и 257, но неверно для простых чисел, находящихся в промежутках между ними. Здесь Мерсенн немного ошибся. Число 267 — 1 не является простым, но зато таковым является число 261 — 1, как и числа 289 — 1 и 2107 — 1, а вот число 2257 — 1 простым не является. Показатели степени меньше 500, при которых разность степени двойки и единицы дает простое число, следующие:

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127.

Наибольшая из этих разностей, состоящая из 39 разрядов, а именно

2127 — 1 = 170 141 183 460 469 231 731 687 303 715 884 105 727,

на самом деле является простым числом, что было лишь в 1876 г. доказано французским школьным учителем Эдуардом Люка. Это самое большое простое число, вычисленное вручную.

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

Пьер де Ферма решил превзойти Мерсенна, с которым состоял в дружеской переписке. Он разработал другую формулу, построенную на следующих рассуждениях: очевидно, что 3 — сумма единицы и двойки — является простым числом, точнее, первым нечетным простым числом. Прибавив 2 к 3, мы получим еще одно простое число 3 + 2 = 5. Ферма перемножил оба числа и прибавил 2. Получилось число 3 × 5 + 2 = 17, а оно тоже является простым. Следующим шагом стало перемножение трех предыдущих простых чисел — получивших в честь первооткрывателя наименование «чисел Ферма» — и прибавление к произведению 2. Теперь Ферма получил действительно довольно большое простое число, а именно

3 × 5 × 17 + 2 = 257.

Ферма и сам был очарован открытым им рецептом. Он прибавил к произведению первых четырех чисел Ферма двойку и получил пятое число Ферма,

3 × 5 × 17 × 257 + 2 = 65 537,

а затем потратил массу усилий на доказательство того, что оно — простое. И оно на самом деле оказалось таковым. После этого Ферма уверовал в универсальность своей формулы. Воодушевленный успехом, он в 1640 г. писал Френиклю де Бесси:

«Но здесь заключено нечто такое, что больше всего меня поражает: я почти полностью убеждён, что числа

1 + 2 = 3, 1 × 3 + 2 = 5, 1 × 3 × 5 + 2 = 17, 1 × 3 × 5 × 17 + 2 = 257, 1 × 3 × 5 × 17 × 257 + 2 = 65537, 1 × 3 × 5 × 17 × 257 × 65 537 + 2 = 4 294 967 297

и следующее, состоящее из двадцати цифр число

1 × 3 × 5 × 17 × 257 × 65 537 × 4 294 967 297 + 2 = 18 446 744 073 709 551 617 и т. д.,

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

Мы видим здесь число 4 294 967 297, вынесенное в начало настоящей главы. Это шестое число Ферма. Даже сегодня для человека, вооруженного лишь карандашом и бумагой, остается практически непосильной задача определить, является это число простым или нет.

Легко перемножить между собой два больших числа. Но выяснить, на какие сомножители можно разложить большое число, — задача весьма и весьма утомительная. В 1732 г., почти через сто лет после письма Ферма, добросовестный швейцарский математик Леонард Эйлер выяснил, что убеждение Ферма оказалось ошибочным — число 4 294 967 297 — шестое число Ферма — делится на 641.

Этот маленький ляпсус никоим образом не умаляет выдающийся талант Ферма к поиску таинственных числовых законов. Между тем были исследованы числа, следующие за числами 4 294 967 297 и 18 446 744 073 709 551 617, и пока среди них простые числа не найдены. Числа Ферма увеличиваются взрывообразно, и поэтому задача поиска среди них простых чисел не из легких.

Долгое время простыми числами просто ради удовольствия занимались увлеченные фанатики чисел, люди не от мира сего, ибо никто не понимал, на что могут сгодиться простые числа. Они просто существовали в царстве чисел, редкие, как золотые самородки в аляскинских реках, но совершенно бесполезные.

В 1970-х гг. совершенно неожиданно выяснилось, что это далеко не так. Простые числа, и прежде всего большие простые числа, оказались неслыханно ценными, более ценными, нежели золото и драгоценные камни. Простые числа могут принести большую власть. Для того чтобы понять это, нам придется погрузиться в сумрачный мир шпионажа.

Мы сейчас переместимся во времена холодной войны, когда, с точки зрения спецслужб, мир еще находился в полном «порядке». Британцы и американцы были на Западе, русские — на Востоке, а между ними был — казалось, навечно — воздвигнут железный занавес. Этот занавес делил мир пополам, и это деление казалось незыблемым.