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

Является ли число 170 141 183 460 469 231 731 687 303 715 884 105 727 простым? Прежде чем искать ответ в Интернете, подумайте, как вы могли бы ответить на этот вопрос без компьютера или даже цифрового калькулятора?

В 1800-х годах французский математик Эдуард Лукас потратил годы на то, чтобы доказать, что это 39-значное число действительно простое. Как он это сделал? Лукас, который, кстати, также придумал увлекательную игру «Ханойская башня», разработал метод, который по-прежнему полезен и сегодня, более чем столетие спустя.

Люди тысячелетиями были очарованы простыми числами. Эти числа делятся только на 1 и на самих себя, в то время как любое другое целое число можно однозначно выразить как произведение нескольких простых чисел; например, 15 = 3 × 5. Простые числа по сути образуют периодическую таблицу математики. Они также хранят в себе много секретов. Они появляются на числовой прямой с определённой регулярностью, но их появление характеризуется колебаниями, которые пока не получается оценить количественно. Эта непредсказуемость вызывает у экспертов что-то вроде беспокойства.

А любители математики постоянно ищут новые простые числа. Текущий рекорд (по состоянию на октябрь 2025 года) для самого большого простого числа составляет 2^{136 279 841} − 1, число с 41 024 320 цифрами. Простое произнесение этого числа вслух заняло бы примерно 240 дней.

Простые числа с особой структурой

Любой, кто следил за рекордными простыми числами последних лет, мог заметить, что они в основном имеют схожую структуру: 2 ^p – 1 (где p — простое число). Простые числа подобного вида называются простыми числами Мерсенна. И число, которому Лукас посвятил почти два десятилетия своей жизни, также является простым числом Мерсенна, а именно 2¹²⁷ – 1. Но в этих простых числах Мерсенна есть одна хитрость: не каждое число вида 2 ^p – 1 является простым числом для каждого простого значения p. Например, 2¹¹ – 1 даёт 2047, что можно записать как произведение 23 и 89.

Поэтому в середине XIX века Лукас задался вопросом, является ли 2¹²⁷ – 1 простым числом. Он столкнулся с огромной проблемой. Это число огромно, состоит из 39 цифр, а в то время Лукас, понятное дело, не имел доступа к компьютеру. Ему пришлось вручную убедиться, что 2¹²⁷ – 1 не имеет делителей (кроме 1 и самого себя).

Один из способов выполнить эту задачу — пройти все простые числа до 2¹²⁷ – 1 и убедиться, что оно не делится ни на одно из них. Но это чрезвычайно трудоёмко и просто невыполнимо, если у вас нет списка всех простых чисел меньше этого.

Тест простых чисел Лукаса-Леммера

Лукас не сдался. Он разработал новый метод, основанный на открытиях своего коллеги Эвариста Галуа, который требовал значительно меньше вычислений.

Прежде чем мы углубимся в прекрасную, но, признаться, абстрактную математику Галуа и Лукаса, я представлю результат Лукаса, который сейчас известен как тест на простоту Лукаса-Леммера.

Чтобы проверить, является ли 2 ^p – 1 простым числом, Лукас разработал следующий алгоритм:

1. Создайте последовательность чисел, первым членом которой является s₀ = 4, а каждый последующий член s_n вычисляется как s²_{n – 1} – 2. Таким образом, последовательность будет следующей: 4, 14, 194, 37634 и так далее.

2. Тогда 2 ^p – 1 является простым числом тогда и только тогда, когда (p – 2)-й член последовательности (то есть s _{p – 2}) делится на 2 ^p – 1 без остатка. То есть каждое простое число Мерсенна имеет это свойство, и, наоборот, каждое s _{p – 2} является простым числом Мерсенна 2 ^p – 1.

Таким образом, вместо того, чтобы делить число Мерсенна на все простые числа, меньшие 2¹²⁷ – 1, достаточно выполнить вычисления, чтобы найти s₁₂₅, а затем разделить на 2¹²⁷ – 1. Это гораздо проще, верно?

На практике есть только одна маленькая — или, скорее, очень большая — проблема. Члены последовательности s_n растут чрезвычайно быстро — настолько быстро, что работать с ними не особенно практично. Поэтому эксперты прибегают к хитрости: они делят члены последовательности s_n на число Мерсенна и продолжают работать с остатком деления, если деление не даёт целого числа. Это не меняет вторую часть алгоритма, поэтому условие для простых чисел Мерсенна остаётся прежним: они должны делиться на s _{p – 2} без остатка. Однако эта хитрость значительно уменьшает s _{p – 2}.

Чтобы лучше понять тест на простоту, мы можем рассмотреть его на простом примере: возьмём число Мерсенна 2⁵ – 1, которое равно 31. Используя алгоритм, разработанный Лукасом, нам нужно вычислить s₃, которое равно 37634. Деля это число на 31, мы получаем точный результа�� 1214. Это означает, что s₃ делится на 2⁵ – 1, и, следовательно, последнее является простым числом.

После многих лет кропотливой работы Лукас разработал этот тест на простоту и применил его к 2¹²⁷ – 1. Таким образом, он смог показать, что это действительно простое число. На сегодняшний день оно остаётся самым большим простым числом, найденным без помощи компьютера.

Однако Лукас не доказал окончательно, что его метод надёжно идентифицирует простые числа Мерсенна. Это удалось сделать только математику Деррику Генри Лемеру в 1930 году, поэтому метод известен как тест на простоту Лукаса-Леммера.

Конечные множества чисел

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

Тест на простоту Лукаса-Леммера основан на исследованиях Галуа, который в начале XIX века изучал симметрию различных математических объектов. Однако, в отличие от своих предшественников, он не ограничивался геометрическими фигурами, а также рассматривал симметрию уравнений или числовых полей. Последний термин описывает множество чисел, в котором можно применять все четыре основных арифметических операции (то есть сложение, вычитание, умножение и деление) без выхода за пределы множества. Другими словами, если я сложу или разделил два числа из множества, я получу число, которое также является частью м��ожества. Примерами числовых множеств являются рациональные числа (которые включают целые числа и дроби) или действительные числа.

Но оказывается, что существуют меньшие множества чисел, содержащие только конечное число целых чисел от 0 до p – 1. Чтобы сохранить свойства множества, числа должны периодически повторяться; после числа с номером p – 1 снова следует число с номером 0: (0, 1, 2, 3, ..., p – 1, 0, 1, 2, ...). Такие так называемые конечные поля могут показаться странными, но на самом деле мы сталкиваемся с ними в повседневной жизни: на аналоговых часах вполне естественно за 12 следует 1.

Как оказалось, конечные числовые системы являются полем тогда и только тогда, когда p является простым числом. Галуа обнаружил, что эти конечные числовые поля обладают особыми симметричными свойствами. Лукас использовал этот принцип при разработке своего теста на простоту: если 2¹²⁷ – 1 является простым числом, то соответствующее числовое поле 0, 1, 2,..., 2¹²⁷ – 2 должно обладать определёнными симметричными свойствами. Чтобы сгенерировать эту конечную систему чисел, необходимо разделить все значения, большие чем 2¹²⁷ – 1, на 2¹²⁷ – 1 и вычислить остаток. Это и будет последним шагом в алгоритме Лукаса.