Глава 7. Тайны простых чисел

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

Первые несколько простых чисел – это 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Все числа, не относящиеся к простым, называют составными. Само число 1 простым не считается (а могло бы), поскольку иначе возникли бы сложности с рядом полезных теорем, в том числе с той, которая настолько важна, что ее величают “основной теоремой арифметики”. Она гласит, что любое число можно представить в виде произведения простых чисел единственным способом (если не учитывать порядок следования множителей). Например, 10 = 2 x 5, а 12 = 2 x 2 x 3. Если бы единица считалась простым числом, то таких способов было бы бесконечное множество – ведь можно сколько угодно раз последовательно умножать число на единицу, результат от этого не изменится.

В природе простые числа встречаются в самых удивительных и неожиданных местах. Один из видов цикад, Magicicada septendecim, имеет 17-летний жизненный цикл. Все особи этого вида проводят в стадии личинки ровно семнадцать лет, после чего вся популяция одновременно вылупляется из своих оболочек для спаривания. Другой вид, Magicicada tredecim, имеет 13-летний жизненный цикл. Существует множество теорий, почему в процессе эволюции у этих цикад выработался жизненный цикл, выражающийся простым числом лет. Самая популярная заключается в том, что существовал хищник, тоже появлявшийся раз в определенное количество лет. Если бы цикады достигали зрелости в один год с питающимися ими животными, весь выводок этих насекомых, скорее всего, тут же уничтожался бы. Выживание цикад зависело от способности выработать жизненный цикл, минимально пересекающийся с циклом хищников. Если бы, например, цикл развития того или иного вида составлял пятнадцать лет, то хищники вполне могли бы появляться каждые три года или пять лет и пожирать выводок насекомых всякий раз при его вылуплении; либо появляться каждые шесть или десять лет и уничтожать новое поколение цикад через раз. И в том и в другом случае данный вид цикад в скором времени просто вымер бы. Другое дело, когда жизненный цикл цикад длится семнадцать лет: хищники с более короткой продолжительностью жизни (а по имеющимся данным, гипотетические хищники жили не так долго, как цикады) шестнадцать своих циклов не будут заставать время появления лакомой добычи и в конце концов просто вымрут от истощения. Такие хищники давно бы уже исчезли с лица земли, оставив цикад с их жизненным циклом, выражающимся простым числом лет, живыми-здоровыми.

Цикада.

Известно, что количество простых чисел бесконечно, то есть не существует самого большого простого числа. Евклид доказал это еще две тысячи лет назад. Другое, но очень простое доказательство таково: предположим, что ряд простых чисел не бесконечен. Тогда можно было бы все простые числа перемножить: 2 x 3 x 5 x 7 и так далее, вплоть до самого большого из них. Обозначим получившееся гигантское произведение буквой P и прибавим к нему 1. Теперь у нас есть только два варианта: либо число P + 1 простое, либо оно делится на какое-либо другое, меньшее простое число. Но если разделить P + 1 на любое из простых чисел в нашем списке (а он, как мы условились, включает в себя все существующие простые числа), в остатке всегда останется 1. Это значит, что либо число P + 1 тоже простое, либо оно имеет простой делитель, которого нет в списке. Таким образом, начав с предположения, что существует некое наибольшее простое число, мы пришли к противоречию. В логике и математике этот прием называется “доказательством от противного” (частный случай “доведения до абсурда”, reductio ad absurdum) – когда несостоятельность какого-либо утверждения доказывают, демонстрируя абсурдность его следствий. Значит, исходное предположение неверно, а стало быть, истинно противоположное ему утверждение: существует бесконечное множество простых чисел. Это последнее утверждение называется теоремой Евклида.

В древности математикам нелегко было высчитывать простые числа. В классической Греции точно знали, что 127 – простое, так как это вытекает из “Начал” Евклида. Возмоссчитанное математиком Пьетро Катальди из Болоньи, известным охотником за простыми числами. После публикации трудов французского монаха XVII века Марена Мерсенна, посвятившего немало лет изучению чисел вида 2ⁿ – 1, где n – натуральное (называемых сегодня “числа Мерсенна”), поиск простых чисел сосредоточился именно в этом направлении. Числа Мерсенна – главные подозреваемые, поскольку вероятность, что любое выбранное наугад число из их ряда окажется простым, гораздо выше, чем у других случайных нечетных чисел аналогичной величины (хотя далеко не все числа Мерсенна простые). Первые несколько простых чисел Мерсенна (то есть чисел Мерсенна, которые одновременно являются простыми) – это 3, 7, 31 и 127. Находка Катальди – это девятнадцатое из чисел Мерсенна (M₁₉) и седьмое из простых чисел Мерсенна. Прошло почти полтора столетия, прежде чем швейцарский математик Леонард Эйлер нашел в 1732 году большее простое число. Еще полтора века спустя, в 1876 году, рекорд поставил Эдуард Люка, доказавший, что 127-е число Мерсенна (M₁₂₇), равное приблизительно 170 ундециллионам^[32], также является простым.

Хотя многие из чисел Мерсенна действительно простые, сам Мерсенн допустил в своих расчетах несколько ошибок. Например, он определил как простое число M₆₇. Делители этого числа впервые нашел в 1903 году Фрэнк Нельсон Коул. 31 октября математика пригласили сделать часовой доклад в Американском математическом обществе. Во время лекции Коул, не говоря ни слова, подошел к доске и вручную сначала вычислил значение числа 2⁶⁷ – 1, а затем перемножил 139 707 721 и 761 838 257 287, продемонстрировав, что результаты совпадают, – и молча же вернулся на свое место под гром аплодисментов. Позже он признался, что на то, чтобы найти делители числа 2⁶⁷ – 1, у него ушло “три года воскресений”.

M_74207281, имеющее 22 338 618 знаков. Его вычислил 17 сентября 2015 года Кёртис Купер, профессор Университета Центрального Миссури, в рамках проекта GIMPS (Great Internet Mersenne Prime Search, “Масштабный интернет-проект по поиску простых чисел Мерсенна”) – добровольного совместного проекта распределенных вычислений, участники которого за двадцать с лишним лет его существования уже рассчитали пятнадцать самых больших простых чисел Мерсенна. По сложившейся традиции авторы открытия отметили свой успех, откупорив бутылку шампанского.

Итак, мы знаем, что такое простые числа, и доказали, что их ряд бесконечен. Нам известно, что в современном мире они могут приносить пользу и что они встречаются в природе. Но в области простых чисел еще много белых пятен: например, мы не знаем, верны ли определенные гипотезы. Одна из наиболее известных – проблема Гольдбаха, названная так в честь немецкого математика Христиана Гольдбаха. Гипотеза гласит, что любое четное число, большее двух, можно представить в виде суммы двух простых чисел. Для малых четных чисел это утверждение легко проверить: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 и так далее. С помощью компьютеров были проверены и гораздо большие числа – правило не подвело ни разу. Однако до сих пор неизвестно, верна ли гипотеза Гольдбаха во всех случаях.

Другая недоказанная гипотеза касается пар простых чисел, отличающихся на 2: таких как 3 и 5 или 11 и 13, – их еще называют числами-близнецами. Гипотеза о числах-близнецах гласит, что таких пар – бесконечное множество, однако доказать истинность этого утверждения пока никому не удалось.

Пожалуй, самая большая загадка простых чисел связана с их распределением. Среди малых натуральных чисел простые встречаются очень часто, но с ростом значений – все реже и реже. Математиков интересует, с какой скоростью убывает плотность простых чисел и как много мы вообще способны узнать об их частоте в числовом ряду. Какой-то строгой закономерности в их появлении не наблюдается, но это вовсе не значит, что они выскакивают где попало. В своей книге “Рекорды простых чисел” (The Book of Prime Number Records) Пауло Рибенбойм формулирует это таким образом:

Загадка простых чисел волнует многие поколения математиков. А ведь кажется, куда проще – даже дети в начальной школе могут объяснить, что такое простые числа, назвать несколько первых из них и определить, простое число или нет. Вот и Агниджо заинтересовался простыми числами в очень раннем возрасте, а заодно и кое-какими из нерешенных проблем вокруг них. А со временем этот интерес привел к увлечению другими великими тайнами теории чисел.

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

И действительно, если рассматривать простые числа по одному или маленькими группами, создается ощущение, что закон им не писан. Но если взглянуть на все их множество, в нем, словно в гигантском косяке рыб или стае скворцов, начинает проявляться невидимый вблизи уровень организации. Одно из самых любопытных открытий в области простых чисел было сделано случайно, и мы уже упоминали о нем в предисловии. Произошло это в 1963 году. Заскучав на какой-то лекции, польский математик Станислав Улам начал рисовать на листке бумаги. Он записывал числа в клетки по квадратной спирали, поставив в центре единицу, виток за витком. Затем он обвел кружками все простые числа и обратил внимание на одну странность: по некоторым из диагоналей спирали, а также по нескольким горизонтальным и вертикальным линиям простые числа выстроились необычно густо. Спирали большего размера, построенные с помощью компьютеров и содержащие десятки тысяч чисел, демонстрируют ту же удивительную закономерность. Насколько можно судить, она сохраняется и дальше, какую бы огромную спираль нам ни вздумалось построить.

Часть из таких “плотных” линий спирали соответствует определенным формулам в алгебре, которые, как мы знаем, дают высокий процент простых чисел. Самая известная из них найдена Леонардом Эйлером и названа в его честь. Многочлен Эйлера n² + n + 41 выдает простые числа для всех значений n от 0 до 39. Например, при n = 0, 1, 2, 3, 4 и 5 получаем соответственно 41, 43, 47, 53, 61 и 71. При n = 40 формула дает (не простое) число 41², но при более высоких значениях n продолжает и дальше с завидной частотой выдавать простые числа. Есть и другие похожие формулы, обладающие этим не совсем понятным свойством порождать большое количество простых чисел. Математики продолжают дискутировать по поводу значения закономерностей в спирали Улама и их связи с нерешенными задачами, такими как проблема Гольдбаха, гипотеза о числах-близнецах и гипотеза Лежандра (согласно которой между квадратами двух последовательных натуральных чисел всегда есть простое число). Бесспорно одно: спираль Улама наглядно демонстрирует, что закономерность существует и что, несмотря на кажущуюся беспорядочность распределения простых чисел, они следуют каким-то общим правилам, регулирующим их появление в больших группах.

Спираль Улама.

Самая полезная из известных теорем о распределении простых чисел так и называется – “теорема о распределении простых чисел” – и по праву считается одним из величайших достижений в теории чисел. Если в двух словах, она гласит, что при любом достаточно большом числе N количество простых чисел, меньших N, приблизительно равно N, деленному на натуральный логарифм N. (Натуральный логарифм числа x – это показатель степени, в которую нужно возвести число e, равное 2,718…, чтобы получить x.) Определить, где именно находится следующее простое число, по этой формуле невозможно, зато она дает довольно точное представление о том, как много в заданном интервале простых чисел, при условии что он достаточно велик.

В отличие от теоремы Евклида о бесконечности множества простых чисел, которую, как мы видели, можно доказать за минуту простыми словами, на доказательство теоремы о распределении простых чисел ушло целое столетие. Впервые, в 1792 или 1793 году, закономерность заметил немец Карл Гаусс, еще подростком, а спустя несколько лет, независимо от него, – француз Адриен-Мари Лежандр. Математики, конечно, уже давно знали, что интервалы между простыми числами увеличиваются с ростом значений, но после того, как во второй половине XVIII века были опубликованы расширенные таблицы простых чисел и более точные логарифмические таблицы, поиски конкретных формул, описывающих это уменьшение плотности, оживились. Гаусс и Лежандр обратили внимание, что плотность простых чисел близка к величине, обратно пропорциональной логарифму. Дальнейшее важное развитие эта работа по поиску функции распределения получила в трудах русского математика Пафнутия Чебышёва в период с 1848 по 1850 год. Но самый важный прорыв произошел в 1859 году, когда немец Бернхард Риман опубликовал свою статью “О числе простых чисел, не превышающих данной величины” (единственную его статью на данную тему). На восьми страницах ученый изложил свое предположение, позже названное гипотезой Римана, которое по сей день будоражит умы математиков, пытающихся его доказать. Считается, что Давид Гильберт как-то сказал: если ему суждено будет заснуть на тысячу лет, первое, чем он поинтересуется после пробуждения, – доказана ли уже гипотеза Римана. В своей книге о теории, на которой основано предположение Римана, американский математик Гарольд Эдвардс пишет:

О том, какое огромное значение имеет гипотеза Римана для науки, говорит тот факт, что она вошла в число семи “задач тысячелетия”, определенных Математическим институтом Клэя, – за решение каждой назначена премия в 1 000 000 долларов. Это одна из двух проблем, которые особенно хотелось бы решить Агниджо. Вторая – проблема равенства классов P и NP (мы обсуждали ее в пятой главе). Кроме того, гипотеза Римана – единственная “задача тысячелетия”, что также вошла и в составленный Давидом Гильбертом список из двадцати трех кардинальных проблем математики, представленный им на II Международном конгрессе математиков в Париже 8 августа 1900 года.

Чтобы понять принцип распределения простых чисел, Риман применил методику недавно появившегося раздела математики – комплексного анализа. Как явствует из названия, этот раздел изучает различные способы работы с комплексными числами – теми, что состоят из действительной и “мнимой” частей, например 5 – 3i, где i – квадратный корень из –1. В основе комплексного анализа лежит изучение комплексных функций, то есть попросту правил, с помощью которых можно одно множество комплексных чисел преобразовать в другое. Еще в 1732 году великий швейцарский математик Леонард Эйлер, чье творчество поражает своим объемом и разносторонностью (его научное наследие насчитывает более 31 000 страниц), ввел в математическую науку доселе неизвестное понятие дзета-функции. Она представляет собой разновидность бесконечного ряда – бесконечной суммы элементов, которая, в зависимости от конкретных чисел, составляющих эти элементы, может сходиться или не сходиться к конечному значению. При определенных условиях дзета-функция сводится к ряду, похожему на гармонический (1 + S +  1/3  + j + …), который изучался математиками с античных времен, когда Пифагор и его ученики были одержимы идеей подчинить вселенную законам чисел и музыкальной гармонии. Риман распространил эйлеровскую дзета-функцию на комплексные числа – а потому сегодня она известна также как дзета-функция Римана.

В своей знаменитой статье 1859 года Риман предложил улучшенную, как он считал, формулу для оценки количества простых чисел вплоть до заданного числа. Однако для применения формулы нужно было знать, при каких значениях дзета-функция Римана равна нулю. Дзета-функция Римана определена для всех комплексных чисел вида x + iy, кроме случаев, когда x = 1. Функция равна нулю при всех отрицательных четных целых значениях (–2, –4, –6 и так далее), но для решения вопроса о распределении простых чисел они не представляют интереса, поэтому эти нули называют “тривиальными”. Риман понял, что функция также имеет бесконечное число нулей в критической полосе между x = 0 и x = 1 и что эти “нетривиальные” нули симметричны относительно прямой x = S. Его знаменитая гипотеза гласит, что все нетривиальные нули комплексной дзета-функции как раз находятся точно на этой прямой.

Если гипотеза Римана верна, из этого будет следовать, что в пределах, установленных теоремой о распределении простых чисел, те распределены максимально регулярно. Другими словами, допуская, что есть некая доля “шума” или “хаоса”, которая мешает точно предсказать, где появится следующее простое число, гипотеза Римана говорит нам, что шум этот очень четко регламентирован, что кажущаяся анархия в рядах простых чисел на деле тщательно срежиссирована. Можно для примера представить себе игральную кость со множеством граней, у которой вероятность выпадения простого числа составляет 1/log n. Предположим, что для каждого n, равного или большего 2, вы бросаете кость n раз. В идеале простое число должно выпасть n/log n раз. Но идеал, как известно, недостижим, поэтому в реальности всегда будет отклонение от ожидаемого значения – погрешность. Величина этой погрешности определяется правилом, которое называют законом больших чисел. В гипотезе Римана утверждается, что распределение простых чисел отклоняется от n/log n не больше, чем это следует из закона больших чисел.

Есть немало веских аргументов, свидетельствующих об истинности гипотезы Римана. Риман сам проверил несколько первых нетривиальных нулей на соответствие правилу, а Алан Тьюринг с помощью одного из первых компьютеров протестировал первую тысячу. В 1986 году было объявлено, что первые миллиард с половиной нетривиальных нулей дзета-функции Римана находятся точно на критической прямой, где действительная часть функции равна S. Гораздо раньше, еще в 1915 году, Годфри Харолд Харди доказал, что число нетривиальных нулей на этой прямой бесконечно (хотя и не факт, что все нетривиальные нули лежат именно на ней). В 1989 году американский математик Брайан Конри представил доказательство, что число нулей, лежащих на критической прямой, превышает две пятых от общего количества нулей в критической полосе. Шестью годами позже, после нескольких лет работы проекта распределенных вычислений ZetaGrid, было получено подтверждение того, что первые 100 миллиардов нулей дзета-функции Римана приходятся ровно на критическую прямую, без каких бы то ни было исключений.

Учитывая, что все говорит в пользу истинности гипотезы Римана, сомнения в ее правильности могут показаться невиданным упрямством. Однако в математике между уверенностью и убедительным доказательством – дистанция огромного размера. В отсутствие строгого доказательства даже самые ценные для науки результаты, базирующиеся на предположении теоретика как на чем-то само собой разумеющемся, пусть и такого выдающегося теоретика, как Бернхард Риман, – не более чем карточный домик. Пока существует возможность, что хотя бы один нетривиальный нуль в критической полосе находится где угодно, но не на прямой x = S, любые попытки полагаться на замечательную догадку Римана как на истину означают, что мы выдаем желаемое за действительное.

Между тем важность доказательства истинности (или ложности) гипотезы Римана выходит за рамки не только теории чисел, но и математики в целом. Оказалось, что существует неочевидная, но прямая связь между предположением Римана и субатомным миром. Однажды в апреле 1972 года в Принстоне двое математиков из Института перспективных исследований, Хью Монтгомери и Атле Сельберг, обсуждали недавнее открытие Монтгомери, связанное с интервалами между нетривиальными нулями на критической прямой. Позже, в институтской столовой, Монтгомери познакомили с Фрименом Дайсоном, профессором Школы естественных наук того же института. Стоило Монтгомери затронуть тему своей работы, как Дайсон тут же осознал, что упомянутые расчеты в точности повторяют те, которые ему самому пришлось проводить в 1960-х годах, когда он изучал так называемую теорию случайных матриц. Эта теория используется, чтобы рассчитывать энергетические уровни частиц внутри тяжелых атомных ядер. Дайсон вспоминал удивление, которое он испытал, обнаружив, что при изучении распределения простых чисел всплывают те же самые уравнения:

Нам часто кажется, что некоторые вещи в математике, такие как гипотеза Римана, совершенно оторваны от жизни и не представляют никакого интереса – этакая интеллектуальная эквилибристика. И тем не менее вот вам живой пример (и их не так уж мало) прямой связи между чистой, казалось бы, математикой, и фундаментальными основами физической вселенной.

Больше ста пятидесяти лет прошло с тех пор, как Риман представил миру свою гипотезу. Отсутствие ее доказательства стало зияющей дырой в самом сердце математики. Возможно, решение этой задачи требует идей настолько передовых и радикальных, что они пока лежат за пределами нашего понимания. Если это так, то сами попытки доказать ее могут привести к разработке новых эффективных математических методик. Если доказательство все-таки отыщется, его значение для математической науки будет трудно переоценить – из-за той основополагающей роли, которую простые числа играют в общей системе чисел и из-за их связи со множеством других задач в этой области. Сотни теорем либо устоят, либо рухнут, признанные ложными, в зависимости от того, будет гипотеза Римана доказана или опровергнута. В случае ее доказательства возникнет масса других вопросов, в том числе и “Почему простые числа балансируют на такой зыбкой грани между случайностью и порядком?”. В случае опровержения все эти теоремы падут, а математика будет подвергнута тяжелейшим испытаниям, которые подорвут самые ее основы.

Никто не рассчитывает, что гипотезу Римана докажут со дня на день. Но в математике случается порой, что доказательства появляются неожиданно, без всякого предупреждения. Именно так произошло, когда Эндрю Уайлс представил блестящее доказательство Великой теоремы Ферма^[33]. То же позже произошло и с открытием, относящимся к гипотезе о числах-близнецах – представлении (которое многие считали верным), что существует бесконечное множество пар таких чисел. В 1849 году французский математик Альфонс де Полиньяк пошел еще дальше и предположил, что существует бесконечное количество пар простых чисел, отличающихся на любое конечное число, не только на 2. Долгое время никому не удавалось добиться особых успехов в доказательстве этой гипотезы, пока в 2013 году неизвестный в широких математических кругах преподаватель Университета Нью-Гэмпшира по имени Итан Чжан совершенно неожиданно не опубликовал статью, взбудоражившую научный мир. Чжану удалось доказать, что существует число N, меньшее 70 миллионов, такое, что есть бесконечно много пар простых чисел, разность которых не более N. Это означает, что, как бы далеко мы ни забрались в бескрайний мир больших, огромных и гигантских простых чисел, как бы ни редели постепенно их ряды, мы всегда сумеем найти пары простых чисел, отличающихся друг от друга не больше, чем на 70 миллионов. Есть все основания считать, что этот промежуток можно существенно сократить^[34]. И мы вправе надеяться, что в скором времени в теории простых чисел нас ждут знаменательные открытия.

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