Самое большое простое число: 41 миллион цифр

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

Простое число делится только на 1 и на само себя. Первые простые: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Единица простым не считается, а 2 единственное чётное простое число.

Простые числа как атомы для умножения. Любое натуральное число больше единицы раскладывается на простые множители, причём единственным образом: 60 = 2 · 2 · 3 · 5, и другого набора простых, дающего 60, нет. Это называют основной теоремой арифметики.

Проверить, простое ли небольшое число, легко: достаточно попробовать поделить его на простые числа, не превосходящие корня из него. Для 97 корень меньше 10, значит, проверяем 2, 3, 5, 7. Ни одно не делит, 97 простое. А вот 91 легко принять за простое, но 91 = 7 · 13.

Почему простых бесконечно много

Это доказал ещё Евклид около 300 года до нашей эры, и его доказательство считается одним из самых красивых в математике. Оно помещается в несколько строк.

Предположим, что простых чисел конечное количество, и мы выписали их все: p₁, p₂, …, pₙ. Перемножим их и прибавим единицу.

N = p₁ · p₂ · … · pₙ + 1

На любое из выписанных простых N делится с остатком 1. Значит, либо N само простое, либо делится на какое-то простое, которого нет в нашем списке. В обоих случаях список был неполным. Противоречие, а значит, простых бесконечно много.

Например, 2 · 3 · 5 · 7 + 1 = 211, и это простое число. А 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30 031 = 59 · 509: число составное, но его множители 59 и 509 тоже не входили в исходный список.

Числа Мерсенна

Почти все рекордные простые имеют вид 2ⁿ − 1. Их называют числами Мерсенна, в честь французского монаха XVII века, который их изучал. Например, 2³ − 1 = 7, 2⁵ − 1 = 31, 2⁷ − 1 = 127, всё простые. Но не всегда: 2¹¹ − 1 = 2047 = 23 · 89.

Почему ищут именно их? Для таких чисел есть особенно быстрая проверка, тест Люка–Лемера. Для произвольного числа с миллионами цифр проверка заняла бы немыслимое время, а для числа Мерсенна её можно выполнить за дни.

2¹³⁶ ²⁷⁹ ⁸⁴¹ − 1

Это и есть рекорд 2024 года. С 1996 года поиском занимается проект GIMPS: тысячи добровольцев по всему миру отдают свободное время своих компьютеров на проверку кандидатов. Новый рекорд нашёл Люк Дюрант, который арендовал вычислительные мощности в облаке и запускал проверку на видеокартах. Предыдущий рекорд держался почти шесть лет.

Насколько оно большое

41 миллион цифр трудно представить. Если печатать по три тысячи цифр на странице, понадобится больше тринадцати тысяч страниц, это несколько десятков толстых томов. Чтобы просто произнести число вслух по цифре в секунду без перерывов, потребовалось бы больше года.

Для сравнения: число атомов в видимой Вселенной оценивают числом примерно с 80 цифрами. Рекордное простое больше этого настолько, что сравнение теряет смысл.

Зачем это нужно

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

Есть и нерешённые загадки. Гипотеза о простых-близнецах утверждает, что пар простых, отличающихся на 2, вроде 11 и 13 или 17 и 19, бесконечно много. Доказать её не могут уже больше ста лет. В 2013 году математик Итан Чжан доказал, что бесконечно много пар простых, расстояние между которыми меньше 70 миллионов. Потом совместными усилиями границу опустили до 246. До двойки пока не дошли.

Попробуйте сами

Задачи на делимость и простые числа встречаются и в олимпиадах с 5 класса, и в последнем задании профильного ЕГЭ. Признаки делимости собраны в отдельной таблице.

Частые вопросы