Французский учёный посвятил десятилетия подтверждению простоты этого гигантского числа — метод остаётся актуальным спустя полтора века.
Можно ли считать число 170 141 183 460 469 231 731 687 303 715 884 105 727 простым? Прежде чем обращаться к поисковикам, представьте, как вы проверили бы это вручную, без компьютера и калькулятора.
В XIX веке Эдуар Лукас потратил годы на доказательство простоты 39-значного числа 2⁽¹²⁷⁾−1. Как ему это удалось? Лукас, также известный как автор головоломки «Ханойская башня», предложил алгоритм, который и сегодня входит в инструментарий математики.
На протяжении тысячелетий учёные увлечены простыми числами — теми, что делятся лишь на 1 и на само себя. Любое другое число раскладывается на их произведение, например, 15 = 3 × 5. Простые подобны «таблице Менделеева» для арифметики: они располагаются по определённым закономерностям, но с непредсказуемыми отклонениями, что даёт простор для исследований.
По состоянию на октябрь 2025 года рекорд принадлежит числу Мерсенна 2⁽¹³⁶₂₇₉₈₄₁⁾−1, содержащему 41 024 320 цифр. Его словесное воспроизведение заняло бы около 240 дней.
Числа Мерсенна и их свойства
В поисках самых крупных простых чисел чаще всего встречаются выражения 2ᵖ−1, где p — простое. Они получили название чисел Мерсенна. Однако не каждое число этого вида является простым: при p=11 мы получаем 2047=23×89.
Лукас поставил перед собой задачу: проверить, прост ли M=2¹²⁷−1. Без компьютеров ему оставалось вручную убедиться, что у M нет нетривиальных делителей, что представляло собой невыполнимую задачу при прямом переборе.
Тест Лукаса–Леммера
Чтобы обойти трудоёмкий поиск делителей, Лукас разработал алгоритм на основе работ Эвариста Галуа. Суть теста для M=2ᵖ−1:
- Инициализируется последовательность: s₀=4; затем sₙ = (sₙ₋₁)² − 2.
- Число M простое тогда и только тогда, когда при вычислении sₚ₋₂ остаётся нулевой остаток по модулю M — то есть sₚ₋₂ ≡ 0 (mod M).
Вместо прямых вычислений больших квадратов и вычитаний, каждый элемент sₙ берут по модулю M сразу, что делает процесс управляемым.
Например, для p=5: M=31. Вычисляем s₀=4, s₁=14, s₂=194, s₃=37 634. Деление 37 634 на 31 даёт целое, значит 31 действительно простое.
С помощью этого алгоритма Лукас без единого электронного устройства доказал простоту 2¹²⁷−1 — крупнейшего ручного открытия простого числа. Окончательный строгий анализ метода выполнил Деррик Леммер в 1930 году, за что тест получил название Лукаса–Леммера.
Математические основы
Алгоритм опирается на свойства конечных полей GF(p), где p — простое. В таких полях операции сложения, вычитания, умножения и деления (кроме деления на 0) замкнуты на множестве {0,1,…,p−1}. Галуа показал, что эти поля обладают особыми симметриями, что и лежит в основе теста для чисел Мерсенна.
