Во Франции времен кардинала Ришелье, когда знатные люди и богатые буржуа имели достаточно досуга для бесполезных, на первый взгляд, занятий, некоторые из них по-любительски — в лучшем смысле этого слова — занимались проблемой простых чисел. К числу таких людей принадлежали работавший на монетном дворе чиновник Министерства финансов Бернар Френикль де Бесси, образованный монах ордена «минимов» Марен Мерсенн и адвокат и парламентский советник Пьер де Ферма. Все они главным образом пытались отыскать формулу, согласно которой можно было бы получать простые числа.

Один из обманчивых рецептов, разработанный ими, гласил: для того чтобы получить простое число, надо взять число, сложить его с его квадратом и с числом 41. На первый взгляд такой принцип выглядит многообещающе. Действительно, если взять единицу, прибавить к ней квадрат единицы, то есть 1, а затем 41, то получится 43 — простое число. Если взять 2, то его квадрат равен 4. При сложении обоих чисел с 41 получится простое число 47. Взяв 3, мы получим 53, также простое число. Далее, если взять 4 и 5, то получатся тоже простые числа — 61 и 71 соответственно. Этот ряд не кончается долго. Например, возьмем число 10, возведем его в квадрат, сложим 100 и 10 и прибавим 41. Мы опять получим простое число — 151. Если взять число 36, прибавить 36² = 1296, а затем еще число 41, то получится простое число 1373. По этой формуле числа от 1 до 39 бесперебойно дают простые числа. Но потом система дает сбой. Прибавим к числу 40 его квадрат, 40² = 40 × 40, и в результате получим число, равное произведению 40 × 41. Если же к этому числу прибавить число 41, то получится число 41 × 41 = 41². Это число не может быть простым. (Это просто прекрасно, что для обоснования этого утверждения не надо ничего вычислять. Однако, разумеется, с тем же успехом можно указать на то, что сложение числа 40 с его квадратом 40² = 1600 дает в результате 1640, после увеличения которого на 41 мы получим число 1681. Можно легко удостовериться в том, что 1681 = 41² = 41 × 41, то есть не является простым числом. Но доказательство, позволяющее избежать вычислений, выглядит все-таки более изящно.)

Марен Мерсенн нашел еще один рецепт. Он вычитал из степеней 2, то есть из чисел

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

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

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

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

являются простыми. Мерсенн утверждал, что то же самое верно и для показателей степени 31, 67, 127 и 257, но неверно для простых чисел, находящихся в промежутках между ними. Здесь Мерсенн немного ошибся. Число 2⁶⁷ — 1 не является простым, но зато таковым является число 2⁶¹ — 1, как и числа 2⁸⁹ — 1 и 2¹⁰⁷ — 1, а вот число 2²⁵⁷ — 1 простым не является. Показатели степени меньше 500, при которых разность степени двойки и единицы дает простое число, следующие:

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

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

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

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

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

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

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

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

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

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

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

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

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

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