Синергия Онлайн-школа
предметная библиотека2 мин чтения

Что такое числа Мерсенна и зачем ищут большие простые числа

Редакция Школьного Университета «Синергия»

Редакция онлайн-школы для 5–11 классов

Простое число больше единицы делится без остатка только на единицу и на себя. Числа Мерсенна получают по формуле 2ⁿ − 1, где n — натуральное число. Среди них встречаются простые числа, но сама формула простоты не гарантирует.

Проверим четыре показателя

При n = 2 получается 3, при n = 3 получается 7. Оба числа простые. При n = 4 получается 15, которое делится на 3 и на 5. Возьмём n = 11, это простой показатель. Получим 2 047, но 2 047 = 23 × 89. Значит, даже простой показатель даёт лишь кандидата на проверку.

Почему составные показатели можно пропускать

Если n = a × b, то 2ⁿ − 1 можно переписать как (2ᵃ)ᵇ − 1. Выражение xᵇ − 1 делится на x − 1. Например, 2⁶ − 1 = 8² − 1 = 7 × 9. При a и b больше единицы так находят нетривиальный делитель. Это экономит усилия при поиске.

Как ищут очень большие числа

Простых чисел бесконечно много, поэтому самого большого простого числа не существует. У проектов поиска есть меняющийся рекорд среди уже найденных. Числа Мерсенна интересны тем, что для них разработаны специальные тесты простоты. Подробности объясняет проект GIMPS. Для самопроверки вычислите 2⁵ − 1 и решите, на какие простые числа достаточно проверить делимость. Получается 31, а до его квадратного корня есть только 2, 3 и 5.

читайте также

предметная библиотека

Режим дня школьника с первой и второй сменой

Два примера расписания, способ расставить кружки и проверка, помещается ли домашняя работа в обычный день.

предметная библиотека

Как вернуться к учёбе после каникул за пять дней

План на первые учебные дни и способ различить усталость, забытые темы и проблемы с расписанием.

предметная библиотека

Как подготовиться к контрольной по математике и русскому

Два плана тренировки, примеры самопроверки и способ понять, какие ошибки разбирать в первую очередь.

← все материалы блога