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

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

БесплатноБез регистрацииМгновенный результат

Проверка Простого Числа МерсеннаПопробуйте — бесплатно ▼

Лукас–Лемер: M_p простое, если s → s² − 2 доходит до 0

Введите ниже показатель p, чтобы проверить, является ли 2^p − 1 простым числом Мерсенна, с ходом теста Лукаса–Лемера и битовой записью.

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. Оно равно $2^{31} - 1$, потому что в 32-битном целом в дополнительном коде под модуль отводится 31 бит; то, что это число ещё и простое, — чистое совпадение.
Между последовательными простыми числами Мерсенна существуют промежутки неизвестного размера. Неизвестно, существует ли бесконечно много простых чисел Мерсенна — гипотеза Ленстры — Померанса — Вагстаффа предсказывает, что их бесконечно много и они растут примерно как $e^\gamma \log_2 p$.
В 2008 году фонд Electronic Frontier Foundation присудил 100 000 долларов США первому первооткрывателю простого числа из 10 миллионов цифр. Приз достался команде GIMPS из UCLA за $M_{43112609}$. Приз в размере 150 000 долларов США все еще доступен для первого простого числа из 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 г.

Основные математические операции:

Калькулятор абсолютного значения Новый
Проверка Дружественных Чисел Новый
Визуализатор переноса и заёма Новый
Калькулятор функций потолка и пола Новый
Калькулятор общего множителя
Калькулятор перекрёстного умножения Новый
Калькулятор куба и кубического корня
Калькулятор кубического корня
Калькулятор Цифрового Корня Новый
Разделение на две части
Калькулятор делимого теста
Калькулятор египетского умножения Новый
Калькулятор Оценки Новый
Проверка четного или нечетного числа Новый
Калькулятор фактора
Проверка числа Фибоначчи Новый
Калькулятор минимума и максимума
Первые n цифр числа e
Первые n цифр числа Пи
Верификатор гипотезы Гольдбаха Новый
Калькулятор наибольшего общего делителя
Это простое число?
Калькулятор наименьшего общего кратного (НОК)
Калькулятор сложения и вычитания столбиком Новый
Калькулятор деления столбиком Популярное
Калькулятор Умножения в Столбик Новый
Калькулятор функции Мёбиуса Новый
Тренажёр Устного Счёта Новый
Проверка Простого Числа Мерсенна Новый
Калькулятор модуля Популярное
Калькулятор умножения
Генератор таблицы умножения Новый
Калькулятор корня n-й степени
Генератор разложений чисел Новый
Калькулятор количества цифр Популярное
Поиск Числовых Закономерностей Новый
Калькулятор порядка операций PEMDAS Новый
Проверка Совершенных Чисел Новый
Генератор таблицы разрядных значений Новый
Калькулятор простого множителя
Калькулятор разложения на простые множители
Частное и калькулятор остатка
Генератор Случайных Математических Задач Популярное
Калькулятор соотношений Новый
Калькулятор математики с римскими цифрами Новый
Умножение Русских Крестьян Новый
Генератор Счёта с Пропуском Новый
Симулятор Соробан — Японские Счёты Новый
Сортировка чисел
Калькулятор квадратного корня Популярное
Калькулятор Суммы
Тест на таблицу умножения Новый
Калькулятор цены за единицу Новый
Калькулятор Ведической Математики Новый

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

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

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

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

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

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

Двоичный код

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

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

Проект GIMPS

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

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

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

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

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

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

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

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

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

Основные математические операции:

Решение по математике

Числа и делители

Дроби и деление

Степени, корни и логарифмы

Алгебра и уравнения

Математический анализ

Геометрия и тригонометрия

Популярные и обновлённые инструменты:

Скачайте всё одним ZIP-архивом с Pro