Числа Мерсенна

Числа Мерсенна  — числа вида Mn=2n1, где n — натуральное число. Эти числа примечательны тем, что некоторые из них являются простыми. Названы в честь французского математика Марена Мерсенна, исследовавшего их свойства в XVII веке.

Определения


Числа Мерсенна в широком смысле — числа вида Mn=2n1, где n — натуральное число.
 Числа Мерсенна Mn при n=1,2,3, образуют последовательность:

  1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16 383, 32 767, , 131 071, \ldots
  Иногда числами Мерсенна называют только числа вида Mp=2p1 с простым показателем p. Эта последовательность начинается так:

  3, 7, 31, 127, 2047, 8191, 131 071, 524 287, 8 388 607, 536 870 911, , 137 438 953 471, \ldots
Простое число Мерсенна  — простое число вида Mn=2n1, где n — натуральное число, то есть числа Мерсенна, являющиеся простыми. Для всех простых чисел вида 2n1 показатель степени n также всегда является простым числом, поэтому простые числа Мерсенна корректно определены вне зависимости от выбранного определения чисел Мерсенна. Простые числа Мерсенна образуют последовательность:

 , , , , , , , , , , , , \ldots
  Показатели p простых чисел Мерсенна образуют последовательность:

  2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, , , , , , , , , , , , , , , , , , , , , , , , \ldots .

Свойства чисел Мерсенна



  • Для всех Mn справедливо, если n составное, то и Mn тоже составное, что следует из:

2n1=2kl1=(2k1)(2k(l1)+2k(l2)++1),

 где kl=n.
 Отсюда сразу следует: если Mn является простым, то число n также простое. Обратное утверждение в общем случае неверно, наименьшим контрпримером является M11=2047=2389.

  • Любой делитель числа Mp для простого p имеет вид 2pk+1, где k — натуральное число (это является следствием малой теоремы Ферма).
  • Каждое чётное совершенное число имеет вид Mp(Mp+1)2=2p1(2p1), где число Мерсенна Mp является простым (это утверждение доказано Эйлером).

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


 Числа Мерсенна получили известность в связи с эффективным тестом простоты больших чисел — тестом Люка — Лемера. Поэтому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа.
 Самым большим известным простым числом (на декабрь 2016) является число Мерсенна M74207281=2742072811, найденное 7 января 2016 года Кертисом Купером в рамках проекта распределённых вычислений GIMPS. Десятичная запись числа M74207281 содержит цифр.
 всего известно 49 простых чисел Мерсенна. При этом порядковые номера достоверно установлены только у первых 45 чисел. В частности, неизвестно, существуют ли другие простые числа Мерсенна, меньшие известного рекордного.
 Интересно отметить, что 45-е простое число Мерсенна M37156667 было найдено на две недели позднее 47-го известного простого числа Мерсенна M43112609, а 46-е известное простое число Мерсенна M42643801 было найдено только через год.
 За нахождение простого числа Мерсенна M43112609 проектом GIMPS в 2009 году была вручена премия в 100 000 долларов США, назначенная сообществом Electronic Frontier Foundation за нахождение простого числа, десятичная запись которого содержит не менее 10 миллионов цифр.

Вариации и обобщения



  • Двойные числа Мерсенна определяются как MMn=22n11. известны только 4 простых числа такого вида (при n = 2, 3, 5, 7).
  • Обобщённые числа Мерсенна. Так как число 2n1 можно представить в виде суммы n первых членов возрастающей геометрической прогрессии:

2n1=20+21+22++2n1=2n121,

 возможно определить обобщённые числа Мерсенна:
h0+h1+h2++hn1=hn1h1=Mh,n.

 Числа Мерсенна являются частным случаем обобщенных чисел Мерсенна при h=2.
 При некоторых значениях h,n обобщённые числа Мерсенна являются простыми, например, M3,3,M3,7,M3,13,M3,71,M5,3,M5,7,M5,47 и др.

Открытые проблемы



  • Неизвестно, конечно или бесконечно множество простых чисел Мерсенна и плотность их распределения во множестве натуральных чисел.
  • Неизвестно, является ли число MM61=226111 простым.

Применение


 Простые числа Мерсенна применяются для построения генераторов псевдослучайных чисел с большими периодами, таких как вихрь Мерсенна.