Что такое числа Мерсенна и зачем ищут большие простые числа
Редакция Школьного Университета «Синергия»
Редакция онлайн-школы для 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.
читайте также
предметная библиотека
Режим дня школьника с первой и второй сменой
Два примера расписания, способ расставить кружки и проверка, помещается ли домашняя работа в обычный день.
предметная библиотека
Как вернуться к учёбе после каникул за пять дней
План на первые учебные дни и способ различить усталость, забытые темы и проблемы с расписанием.
предметная библиотека
Как подготовиться к контрольной по математике и русскому
Два плана тренировки, примеры самопроверки и способ понять, какие ошибки разбирать в первую очередь.