Проверка Простого Числа Мерсенна

Проверьте, является ли число 2^p − 1 простым числом Мерсенна для заданного показателя p. Используется тест простоты Люка — Лемера с анимированной трассировкой итераций, визуализацией двоичного кода, сопряжением совершенных чисел Евклида — Эйлера и исторической справкой о 52 известных простых числах Мерсенна.

Embed Проверка Простого Числа Мерсенна Widget

О Проверка Простого Числа Мерсенна

Добро пожаловать в Проверку простого числа Мерсенна — интерактивный инструмент, который проверяет, является ли $2^p - 1$ простым числом Мерсенна для любого показателя $p$ до 5000. Инструмент выполняет знаменитый тест простоты Люка-Лемера, показывает анимированный протокол итераций рекуррентного соотношения $S_i = S_{i-1}^2 - 2 \pmod{M_p}$, визуализирует двоичный код (определяющий признак каждого числа Мерсенна) и — если результат является простым — находит соответствующее четное совершенное число по теореме Евклида — Эйлера.

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

Числом Мерсенна называется число вида $M_p = 2^p - 1$. Когда само $M_p$ является простым, оно называется простым числом Мерсенна. Название дано в честь Марена Мерсенна (1588–1648), французского монаха, который составил список первых случаев и высказал предположение о том, какие показатели до 257 дают простые числа — список, который оказался частично неверным, но положил начало трем векам исследований.

Простое число Мерсенна

$$M_p = 2^p - 1 \;\; \text{является простым, где } p \text{ само должно быть простым}$$

Первые несколько простых чисел Мерсенна по порядку:

$M_2 = 3$
$M_3 = 7$
$M_5 = 31$
$M_7 = 127$
$M_{13} = 8{,}191$
$M_{17} = 131{,}071$
$M_{19} = 524{,}287$
$M_{31} = 2{,}147{,}483{,}647$ (найдено Эйлером в 1772 году — крупнейшее известное простое число на протяжении 104 лет)

По состоянию на 2024 год известно ровно 52 простых числа Мерсенна. Текущий рекорд — $M_{136{,}279{,}841}$, обнаруженное в октябре 2024 года проектом распределенных вычислений GIMPS; это число содержит 41 024 320 десятичных цифр.

Тест Люка-Лемера

Причина, по которой простые числа Мерсенна доминируют в книгах рекордов, заключается в специализированном, чрезвычайно быстром тесте простоты, открытом Эдуардом Люка (1878) и упрощенном Дерриком Лемером (1930):

Тест Люка-Лемера

$$S_0 = 4, \quad S_i = S_{i-1}^2 - 2 \pmod{M_p}$$

Для простого $p \geq 3$: $\;M_p$ простое $\iff S_{p-2} \equiv 0 \pmod{M_p}$

Тест требует всего $p-2$ возведений в квадрат по модулю — примерно $O(p^3)$ битовых операций при обычном умножении или $O(p^2 \log p \log\log p)$ с использованием БПФ (FFT). Сравните это с универсальными тестами простоты для чисел размера $M_p$ (миллионы цифр), которые были бы совершенно невыполнимы. Упрощенный тест Люка-Лемера — это то, что делает поиск простых чисел Мерсенна возможным.

Почему p должно быть простым?

Если $p = a \cdot b$, где $a, b > 1$, классическое тождество показывает, что $2^a - 1$ делит $2^{ab} - 1$:

Тождество факторизации

$$2^{ab} - 1 = (2^a - 1)\left(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1\right)$$

Таким образом, если показатель является составным, то $M_p$ автоматически является составным. Обратное неверно: простота $p$ не гарантирует простоту $M_p$. Например, $p = 11$ — простое число, но $M_{11} = 2047 = 23 \times 89$.

Числа Мерсенна и совершенные числа (Евклид — Эйлер)

Евклид заметил около 300 г. до н. э., что если $2^p - 1$ — простое число, то $2^{p-1}(2^p - 1)$ является совершенным числом — числом, равным сумме своих собственных делителей. Позже Эйлер доказал обратное: каждое четное совершенное число возникает именно таким образом.

Теорема Евклида — Эйлера

$$N \text{ — четное совершенное число} \iff N = 2^{p-1}(2^p - 1),\;\; 2^p - 1 \text{ простое}$$

Так что нахождение нового простого числа Мерсенна мгновенно дает новое совершенное число. Первые четыре четных совершенных числа — 6, 28, 496 и 8128 — известны еще со времен античности. Вопрос о том, существует ли хотя бы одно нечетное совершенное число, остается нерешенной проблемой на протяжении более 2300 лет.

Двоичный код

Каждое число Мерсенна имеет уникальное чистое двоичное представление: $2^p$ в двоичном виде — это $1$, за которой следуют $p$ нулей, поэтому $2^p - 1$ — это ровно $p$ последовательных 1-битов:

M_5 = 2^5 − 1 = 11111₂ = 31

M_7 = 2^7 − 1 = 1111111₂ = 127

Вот почему инструмент визуализирует каждый бит как отдельную плитку — битовый узор является визуальной подписью числа Мерсенна, независимо от того, является ли оно простым.

Как пользоваться этим калькулятором

Введите показатель $p$: любое целое положительное число от 1 до 5 000.
Нажмите «Проверить»: инструмент сначала проверяет, является ли $p$ простым; если нет, он объясняет, почему $M_p$ должно быть составным.
Для простого $p$: выполняется рекурсия Люка-Лемера в течение $p - 2$ итераций по модулю $M_p$.
Изучите результат: баннер с вердиктом, протокол итераций (с «...» для пропущенных промежуточных шагов при больших $p$), десятичную и двоичную формы $M_p$, а также соответствующее совершенное число Евклида — Эйлера, если применимо.

Первые двенадцать известных простых чисел Мерсенна

№	Показатель $p$	$M_p = 2^p - 1$	Цифр	Обнаружено
1	2	3	1	Древность
2	3	7	1	Древность
3	5	31	2	Древность
4	7	127	3	Древность
5	13	8,191	4	1456 (анон.)
6	17	131,071	6	1588 Катальди
7	19	524,287	6	1588 Катальди
8	31	2,147,483,647	10	1772 Эйлер
9	61	2.3 × 10^18	19	1883 Первушин
10	89	6.2 × 10^26	27	1911 Пауэрс
11	107	1.6 × 10^32	33	1914 Пауэрс
12	127	1.7 × 10^38	39	1876 Люка

Проект GIMPS

Great Internet Mersenne Prime Search (GIMPS), запущенный в 1996 году Джорджем Вольтманом, — это проект распределенных вычислений, в котором волонтеры жертвуют время своих процессоров для выполнения тестов Люка-Лемера на потенциальных показателях. По состоянию на 2024 год, каждое простое число Мерсенна, начиная с M_35 = M_{1398269} (1996), было обнаружено GIMPS. Один тест Люка-Лемера на современном фронтире (показатели около $10^8$) занимает недели вычислений на GPU.

Интересные факты о простых числах Мерсенна

$M_{31} = 2{,}147{,}483{,}647$ — это самое большое 32-битное целое число со знаком, знаменитое $\texttt{INT\_MAX}$ в языке C. Это не случайно: значение связано с тем, что $M_{31}$ является простым и, следовательно, естественной границей «прямо перед переполнением».
Между последовательными простыми числами Мерсенна существуют промежутки неизвестного размера. Неизвестно, существует ли бесконечно много простых чисел Мерсенна — гипотеза Ленстры — Померанса — Вагстаффа предсказывает, что их бесконечно много и они растут примерно как $e^\gamma \log_2 p$.
В 2008 году фонд Electronic Frontier Foundation присудил 100 000 долларов США первому первооткрывателю простого числа из 10 миллионов цифр. Приз достался команде GIMPS из UCLA за $M_{43112609}$. Приз в размере 150 000 долларов США все еще доступен для первого простого числа из 100 миллионов цифр.
$M_{31}$ изображено на российской памятной банкноте 1811 года номиналом 100 рублей, выпущенной в честь открытия Эйлера — одно из немногих простых чисел, когда-либо напечатанных на валюте.
Поскольку каждое простое число Мерсенна дает совершенное число, человечеству известно ровно 52 четных совершенных числа (соответственно 52 известным простым числам Мерсенна).

Часто задаваемые вопросы

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

Простое число Мерсенна — это простое число вида $2^p - 1$, где $p$ также является простым. Первыми из них являются 3, 7, 31, 127 и 8 191. По состоянию на 2024 год известно 52 простых числа Мерсенна; самое большое известное простое число ($M_{136{,}279{,}841}$) — это число Мерсенна, содержащее более 41 миллиона цифр.

Как работает тест Люка-Лемера?

Для простого показателя $p \geq 3$ определим $S_0 = 4$ и $S_i = S_{i-1}^2 - 2 \pmod{M_p}$. Число Мерсенна $M_p = 2^p - 1$ является простым тогда и только тогда, когда $S_{p-2} \equiv 0 \pmod{M_p}$. Тест состоит из $p - 2$ итераций, каждая из которых представляет собой одно возведение в квадрат по модулю.

Почему p должно быть простым?

Если $p = ab$, где оба множителя больше 1, то $2^p - 1$ делится на $2^a - 1$ (и на $2^b - 1$), поэтому $M_p$ является составным. Обратное неверно: простота $p$ не гарантирует простоту $M_p$. Например, $p = 11$ — простое число, но $M_{11} = 2047 = 23 \times 89$ — составное.

Какова связь между простыми числами Мерсенна и совершенными числами?

Теорема Евклида — Эйлера утверждает, что каждое четное совершенное число имеет вид $2^{p-1}(2^p - 1)$, где $2^p - 1$ — простое число Мерсенна. Таким образом, каждое простое число Мерсенна порождает ровно одно четное совершенное число. Существуют ли нечетные совершенные числа — одна из старейших открытых проблем математики.

Почему M_p в двоичной системе состоит из p последовательных единиц?

Число $2^p$ в двоичной системе — это 1, за которой следуют $p$ нулей. Вычитание 1 превращает все $p$ конечных нулей в 1. Таким образом, $2^p - 1$ в двоичном виде — это ровно $p$ единиц — определяющий визуальный признак каждого числа Мерсенна, будь оно простым или составным.

Какой максимальный показатель может проверить этот инструмент?

Этот инструмент проверяет показатели до 5 000, чтобы итерация Люка-Лемера завершалась в рамках обычного веб-запроса. Для больших показателей (включая фронтир GIMPS в районе $10^8$) требуется специализированное ПО, такое как Prime95, так как один тест может занять недели вычислений на современном GPU.

Дополнительные ресурсы

Ссылайтесь на этот контент, страницу или инструмент так:

"Проверка Простого Числа Мерсенна" на сайте https://ru.miniWebtool.com/проверка-простого-числа-мерсенна/ от MiniWebtool, https://MiniWebtool.com/

от команды miniwebtool. Обновлено: 18 апр. 2026 г.

Вы также можете попробовать наш AI Решатель Математических Задач GPT, чтобы решить ваши математические проблемы с помощью вопросов и ответов на естественном языке.