Как вручную проверить число на простоту

Французский учёный посвятил десятилетия подтверждению простоты этого гигантского числа — метод остаётся актуальным спустя полтора века.

Можно ли считать число 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:

1. Инициализируется последовательность: s₀=4; затем sₙ = (sₙ₋₁)² − 2.
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}. Галуа показал, что эти поля обладают особыми симметриями, что и лежит в основе теста для чисел Мерсенна.

Источник