Как найти самое большое известное простое число
В декабре прошлого года было обнаружено новое самое большое известное простое число, которое оказалось равным 282 589 933 − 1. Десятичная запись этого числа более чем вдвое превышает длину романа Марселя Пруста «В поисках утраченного времени» (самого длинного романа по версии книги рекордов Гинесса) и примерно на семь процентов длиннее предыдущего рекорда. О том, как это произошло, по каким формулам ищут и не находят простые числа, а также зачем они нужны, по просьбе N + 1 рассказывает математик Иван Тельпуховский.
Простые числа, которые вы можете увидеть на форзаце почти любого школьного учебника математики, — это натуральные числа, бóльшие единицы, которые делятся только на себя и на 1. Например, число 3 — простое, а число 6 (= 2 × 3) уже нет.
Простые числа являются «элементарными кирпичиками» в мире всех натуральных чисел, поскольку любое натуральное число можно единственным образом представить в виде произведения простых чисел (с точностью до порядка сомножителей). Скажем, число 90 представляется в виде произведения 2 × 3 × 3 × 5. Это утверждает основная теорема арифметики, известная по крайней мере еще Евклиду, который, однако, не смог дать ей полного доказательства. Доказательство было дано молодым Гауссом лишь спустя более двух тысяч лет.
Разумно задаться вопросом: конечно ли множество простых чисел в числовом ряду? Сможем ли мы представить любое число как произведение, скажем, только чисел 2, 3 и 5? Отрицательный ответ на этот вопрос дал Евклид в девятой книге своих «Начал». Его аргумент оказался столь простым и фундаментальным, что до сих пор является одним из первых строгих математических доказательств, изучаемых в школе.
Действительно, докажем от противного и допустим, что все простые числа могут быть записаны в виде конечного списка p1, ..., pn. Перемножим все числа из списка и прибавим единицу: p1 × ... × pn + 1. Поскольку получившееся число не содержится в нашем списке и, следовательно, не может быть простым, оно должно делиться на простое число. Однако при делении на любое из чисел p1, ..., pn получается остаток 1. Налицо противоречие.
Для знакомых с азами элементарной топологии рекомендуем разобрать занятное доказательство бесконечности простых чисел, предложенное Фурстенбергом.
Мы знаем, что простых чисел бесконечно много, но как часто они встречаются в натуральном ряду? Иными словами, как быстро растут простые числа и можем ли мы найти для них хотя бы приблизительную формулу?
Ответ на этот вопрос был дан в конце 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-го простого числа: pN ~ N lnN. На самом деле, ее можно даже немного улучшить: pN ~ 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 взимно просты, то в соответствующей арифметической прогрессии встретится бесконечно много простых чисел.
В качестве следующего примера можно рассмотреть квадратичные многочлены, то есть вида an2 + bn + c. Например, в XVIII веке Леонард Эйлер заметил, что значения квадратичного многочлена n2 + n + 41 являются простыми для 39 последовательных значений n. Эти явления иллюстрирует скатерть Улама: в ней по спирали из центра записываются последовательные числа (не показаны), и черным среди них помечаются простые:
Обратите внимание, что некоторые диагонали на скатерти отчетливо выделяются среди других: на них много простых чисел. Оказывается, что диагонали на скатерти Улама и представляют собой значения квадратичных многочленов (попробуйте доказать!). Несмотря на эти обнаружения, до сих пор неизвестно о существовании многочлена второй степени (или выше) от одной переменной, который принимал бы бесконечно много простых значений (что никакой такой многочлен не может принимать только простые значения, нетрудно доказать).
Если перейти к случаю нескольких переменных, то оказывается, что существует многочлен, чьи положительные целые значения совпадают со множеством простых чисел. Этот многочлен является «побочным» результатом многолетней деятельности специалистов в теории алгоритмов, направленной на решение десятой проблемы Гильберта, в которой поставил точку ленинградский (тогда) аспирант Юрий Матиясевич в 1970 году. Отметим, что этот многочлен совершенно бесполезен для вычислений.
Недавно в прессе освещалось достижение математика Симона Плуфа, который утверждает, что нашел конкретную формулу, выдающую рекордные 50 (судя по его сайту, уже и все 100) простых чисел подряд. Внимательный взгляд на эту эмпирическую формулу лишний раз показывает, как далеки мы от осмысленного результата по направлению к формуле простых чисел. И несмотря на то, что мы не знаем, что искомой формулы не может быть в природе, мы попытаемся порассуждать о том, почему ее, скорее всего, нет.
Действительно, эта формула должна бы быть очень умной! Ведь промежуток между соседними простыми числами (и, соответственно, соседними значениями формулы) может быть сколь угодно большим (подсказка: рассмотрите числа n! + 2, ..., n! + n), а может быть (бесконечно часто!) ограниченной длины по теореме, доказанной в 2013 году Итаном Чжаном (в идеале длины 2, как утверждает гипотеза о числах-близнецах).
Другим указанием на отсутствие формулы простых чисел может служить современная точка зрения на множество простых чисел как на модель случайного множества. Грубо говоря, простые числа слишком беспорядочно разбросаны среди натурального ряда и про них можно думать как о псевдослучайном множестве. Разумеется, между простыми числами наблюдается структура, например они все (кроме одного) являются нечетными числами, а значит, не могут идти друг за другом. Простые числа являются детерминированным множеством, принадлежность к которому проверяется за полиномиальное время по числу разрядов.
Тем не менее, если не принимать во внимание мультипликативные свойства простых чисел (которые мы перечисляли), то за ними проглядываются свойства случайного множества. Например, верно, что возможные остатки при делении на 10 для простых чисел (это 1, 3, 7 или 9) асимптотически равновероятны. Примечательно то, что в рамках различных моделей, имитирующих простые числа, легко доказываются многие неразрешенные гипотезы, например, все проблемы Ландау.
Примером модели простых чисел является вероятностная модель Крамера, основанная на теореме о распределении простых чисел: множество выбираются случайно таким образом, что его плотность на отрезке от 1 до N равнаяется уже встречавшемуся выражению 1 / lnN. Модель Крамера можно улучшить, если принять во внимание элементарные свойства «настоящих» простых чисел.
Несмотря на то, что все эти модели не доказывают уже известных гипотез, они, вместе с численными экспериментами, позволяют измерить силу предположения или привести к новым плодотворным догадкам. В частности, используя свою модель, Крамер сформулировал знаменитую гипотезу о величине больших промежутков между простыми числами, над которой бьются математики, но к которой пока не подошли вплотную.
Несмотря на то, что математики не могут найти формулу, выражающую все простые числа, хорошо известны простые формулы, значения которых позволяют явно находить очень большие простые числа. Последние двадцать с лишним лет главной такой формулой является 2p-1, чьи значения называются числами Мерсенна. Поиском простых чисел Мерсенна занимается проект добровольных распределенных вычислений GIMPS, о котором мы уже неоднократно писали (например, здесь, здесь и здесь).
Среди других подобных формул можно отметить обобщенные простые числа Ферма, поиском которых занимается похожий проект PrimeGrid.
Эта деятельность имеет мало общего с «атакой» на недоказанные гипотезы о простых числах, которая использует все передовые достижения математики, и больше похожа на своеобразную форму нумизматики (в чем частично признаются создатели). Тем не менее, как и в случае с доказательством гипотезы Римана, новое СБИПЧ (самое большое известное простое число) может принести «охотнику» денежный гонорар (пусть и скорее всего гораздо меньший). Впрочем, в науке это не главное.
Иван Тельпуховский
Она проходит в Японии
Российские школьники выиграли пять золотых и одну серебряную медаль на 64 Международной математической олимпиаде (IMO-2023), которая проходит со 2 по 13 июля в японском городе Тиба. Об этом N + 1 сообщил руководитель команды Кирилл Сухов — преподаватель петербургского Президентского физико-математического лицея (ФМЛ) № 239. Золотых медалей удостоились Александр Гнусов из Кирова (37 баллов), Алиса Волкова из Санкт-Петербурга (37 баллов), Ратибор Коптилин из Новосибирска (36 баллов), Роман Кузнецов из Санкт-Петербурга (36 баллов) и Эльдар Хисамутдинов из Санкт-Петербурга (35 баллов). Серебряную медаль получил Павел Прозоров из Санкт-Петербурга (28 баллов). Из-за международных санкций организаторы олимпиады еще в прошлом году отстранили Россию от участия в ней, но разрешили россиянам состязаться в качестве частных лиц. Если бы российских участников допустили в качестве команды, то в ее активе было бы 209 баллов, что соответствует четвертому месту — после сборных Китая, США и Южной Кореи. Следует отметить, что в предыдущие годы россияне также добивались больших успехов на Международной математической олимпиаде. В 2022 году они завоевали три золотых и три серебряных медали, а в 2021 году — пять золотых и одну серебряную медаль.