2, 3, 5, 7, 11, ..., 282 589 933 − 1

В декабре прошлого года было обнаружено новое самое большое известное простое число, которое оказалось равным 2^82 589 933 − 1. Десятичная запись этого числа более чем вдвое превышает длину романа Марселя Пруста «В поисках утраченного времени» (самого длинного романа по версии книги рекордов Гинесса) и примерно на семь процентов длиннее предыдущего рекорда. О том, как это произошло, по каким формулам ищут и не находят простые числа, а также зачем они нужны, по просьбе N + 1 рассказывает математик Иван Тельпуховский.

Что такое простые числа

Простые числа, которые вы можете увидеть на форзаце почти любого школьного учебника математики, — это натуральные числа, бóльшие единицы, которые делятся только на себя и на 1. Например, число 3 — простое, а число 6 (= 2 × 3) уже нет.

Простые числа являются «элементарными кирпичиками» в мире всех натуральных чисел, поскольку любое натуральное число можно единственным образом представить в виде произведения простых чисел (с точностью до порядка сомножителей). Скажем, число 90 представляется в виде произведения 2 × 3 × 3 × 5. Это утверждает основная теорема арифметики, известная по крайней мере еще Евклиду, который, однако, не смог дать ей полного доказательства. Доказательство было дано молодым Гауссом лишь спустя более двух тысяч лет.

Разумно задаться вопросом: конечно ли множество простых чисел в числовом ряду? Сможем ли мы представить любое число как произведение, скажем, только чисел 2, 3 и 5? Отрицательный ответ на этот вопрос дал Евклид в девятой книге своих «Начал». Его аргумент оказался столь простым и фундаментальным, что до сих пор является одним из первых строгих математических доказательств, изучаемых в школе.

Мы знаем, что простых чисел бесконечно много, но как часто они встречаются в натуральном ряду? Иными словами, как быстро растут простые числа и можем ли мы найти для них хотя бы приблизительную формулу?

Ответ на этот вопрос был дан в конце XIX века и называется теоремой о распределении простых чисел. Чтобы ее сформулировать, обозначим за π(N) количество простых чисел, не превосходящих число N. Теорема утверждает, что функция π(N) ведет себя как функция N / lnN для больших N, где lnN — натуральный логарифм N. Более строго, в пределе, отношение этих функций равно единице:

Теорему можно интерпретировать следующим образом: у наугад выбранного числа от 1 до N шанс оказаться простым асимптотически равен 1 / lnN. Как следствие, мы получаем, что простые числа попадаются чем дальше, тем реже (попробуйте убедиться в этом сами).

Скорость роста простых чисел

Доказать эту теорему позволило развитие комплексного анализа, чьи методы активно используются в теории чисел по сей день. Простого доказательства у теоремы нет, но его идея, принадлежащая Риману, основывается на том, что распределение простых чисел тесно связано с нулями дзета-функции, задаваемой по следующей формуле для s > 1:

(при

 = 1 мы получаем

, который расходится, поэтому функция не определена в данной точке). Например, для

 = 2 мы получаем

π

/6.

Риман показал, что дзета функцию можно доопределить на множество всех комплексных чисел (кроме s = 1), где у нее раскрываются удивительные свойства (взгляните на эти графики: первый, второй, третий и четвертый).

Возвращаясь к неформальной идее доказательства: можно определить функцию-«звуковую волну», которая звучит как логарифмы всех простых чисел (и степеней простых чисел) меньше заданного числа N. Если «прослушать» эту функцию (а именно, применив к ней преобразование, близкое к преобразованию Фурье) и записать услышанные ноты, то ими окажутся нули дзета-функции!

Завершающим моментом доказательства является отсутствие нулей дзета-функции на вертикальной прямой x = 1 на комплексной плоскости. Отметим удивительную связь со знаменитой гипотезой Римана: она утверждает, что нули дзета-функции в полосе 0 ≤ x ≤ 1 расположены только на «критической» прямой x = 1/2. Пользуясь аллегорией, гипотезу Римана можно сформулировать так: «Музыка простых чисел формирует аккорд».

Из теоремы о распределении простых чисел несложно вывести следующую примерную формулу для N-го простого числа: p_N ~ N lnN. На самом деле, ее можно даже немного улучшить: p_N ~ N(lnN + lnlnN − 1). Например, для тысячного простого числа эта формула ошибается уже меньше чем в 1 процент (поэкспериментируйте сами!).

Несмотря на низкий процент ошибки, ее величина растет с N, и даже если допустить, что гипотеза Римана верна, то величина ошибки будет, грубо говоря, порядка корня из N, поэтому подлинное N-ое простое число отыскать становится все сложнее. Более того, точная формула для N-ного простого числа, которая бы позволила его найти за короткое время (например, полиномиальное по числу разрядов), на сегодняшний день неизвестна.

Почему многочлены не помогут

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

Давайте рассмотрим «игрушечный» пример — линейный многочлен f(n) = an + b. Значения такого многочлена называются арифметической прогрессией. Во-первых, очевидно, что если у чисел a и b есть общий делитель (больший единицы), то больше одного простого элемента в прогрессии не появится (к примеру, 3n + 3 всегда будет делиться на 3). Кроме того, ясно, что только простые значения у многочлена f(n) тоже не могут быть, потому что числа f(kb) = a × kb + b = (ak + 1) × b делятся на b для всех k. Как бы то ни было, математиком Дирихле (известным своим принципом) было доказано, что если числа a и b взимно просты, то в соответствующей арифметической прогрессии встретится бесконечно много простых чисел.

В качестве следующего примера можно рассмотреть квадратичные многочлены, то есть вида an² + bn + c. Например, в XVIII веке Леонард Эйлер заметил, что значения квадратичного многочлена n² + n + 41 являются простыми для 39 последовательных значений n. Эти явления иллюстрирует скатерть Улама: в ней по спирали из центра записываются последовательные числа (не показаны), и черным среди них помечаются простые:

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

Если перейти к случаю нескольких переменных, то оказывается, что существует многочлен, чьи положительные целые значения совпадают со множеством простых чисел. Этот многочлен является «побочным» результатом многолетней деятельности специалистов в теории алгоритмов, направленной на решение десятой проблемы Гильберта, в которой поставил точку ленинградский (тогда) аспирант Юрий Матиясевич в 1970 году. Отметим, что этот многочлен совершенно бесполезен для вычислений.

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

Действительно, эта формула должна бы быть очень умной! Ведь промежуток между соседними простыми числами (и, соответственно, соседними значениями формулы) может быть сколь угодно большим (подсказка: рассмотрите числа n! + 2, ..., n! + n), а может быть (бесконечно часто!) ограниченной длины по теореме, доказанной в 2013 году Итаном Чжаном (в идеале длины 2, как утверждает гипотеза о числах-близнецах).

Простые числа как случайные процессы

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

Тем не менее, если не принимать во внимание мультипликативные свойства простых чисел (которые мы перечисляли), то за ними проглядываются свойства случайного множества. Например, верно, что возможные остатки при делении на 10 для простых чисел (это 1, 3, 7 или 9) асимптотически равновероятны. Примечательно то, что в рамках различных моделей, имитирующих простые числа, легко доказываются многие неразрешенные гипотезы, например, все проблемы Ландау.

Примером модели простых чисел является вероятностная модель Крамера, основанная на теореме о распределении простых чисел: множество выбираются случайно таким образом, что его плотность на отрезке от 1 до N равнаяется уже встречавшемуся выражению 1 / lnN. Модель Крамера можно улучшить, если принять во внимание элементарные свойства «настоящих» простых чисел.

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

Примеры частных формул

Несмотря на то, что математики не могут найти формулу, выражающую все простые числа, хорошо известны простые формулы, значения которых позволяют явно находить очень большие простые числа. Последние двадцать с лишним лет главной такой формулой является 2^p-1, чьи значения называются числами Мерсенна. Поиском простых чисел Мерсенна занимается проект добровольных распределенных вычислений GIMPS, о котором мы уже неоднократно писали (например, здесь, здесь и здесь).

Среди других подобных формул можно отметить обобщенные простые числа Ферма, поиском которых занимается похожий проект PrimeGrid.

Эта деятельность имеет мало общего с «атакой» на недоказанные гипотезы о простых числах, которая использует все передовые достижения математики, и больше похожа на своеобразную форму нумизматики (в чем частично признаются создатели). Тем не менее, как и в случае с доказательством гипотезы Римана, новое СБИПЧ (самое большое известное простое число) может принести «охотнику» денежный гонорар (пусть и скорее всего гораздо меньший). Впрочем, в науке это не главное.

Иван Тельпуховский