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

Ссылка: http://ru.wikipedia.org/wiki/Числа_Мерсенна

Материал из Википедии — свободной энциклопедии

Числа Мерсе́нна — числа вида M_n = 2ⁿ - 1, где n — натуральное число. Названы в честь французского математика Мерсенна.

Последовательность чисел Мерсенна начинается так:
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, … (последовательность A000225 в OEIS)

Иногда числами Мерсенна называют числа M_p с простыми индексами p. Эта последовательность начинается так:
3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147483647, … (последовательность A001348 в OEIS)Содержание [убрать]

1 Свойства
2 Простые числа Мерсенна
3 Вариации и обобщения
4 Открытые проблемы
5 Применение
6 Примечания
7 Ссылки

Свойства
Если Mn является простым, то число n также простое.
Любой делитель числа M_p для простого p имеет вид 2pk+1, где k — натуральное число (следствие малой теоремы Ферма).
Каждое чётное совершенное число имеет вид M_p(M_p + 1) / 2 = 2^{p − 1}(2^p − 1), где число Мерсенна M_p является простым (доказано Эйлером).

Простые числа Мерсенна
Числа Мерсенна получили известность в связи с эффективным критерием простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые больши́е известные простые числа.[1] На данный момент самым больши́м известным простым числом является число Мерсенна M_43112609 = 2^43112609 − 1, найденное в августе 2008 года в рамках проекта распределённых вычислений GIMPS. Длина M_43112609 составляет 12978189 десятичных цифр, что позволило GIMPS в 2009 году получить премию в 100000 долларов США, назначенную сообществом Electronic Frontier Foundation за нахождение простого числа, длина которого превышает 10 миллионов десятичных цифр.[2]

Всего известно 47 простых чисел Мерсенна, причём порядковые номера с уверенностью установлены только у первых 40.[3] Интересно отметить, что 46-е найденное простое число Мерсенна было найдено на две недели позднее 45-го найденного простого числа Мерсенна и оказалось меньше его.

Последовательность простых чисел Мерсенна и их показателей начинается так:
M_p: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, … (последовательность A000668 в OEIS)
p: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, … (последовательность A000043 в OEIS)

Сначала разберёмся со следующим - Утверждением:

Если число n, где n=1,3,5, ... , составное, то есть n=ab, где a и b нечётные целые числа, то число Мерсенна 2ⁿ-1 с индексом n составное и делится на числа Мерсенна с индексами a,b..

То есть 2ⁿ-1 делится на 2^a-1 и делится на 2^b-1

Что даёт это утверждение? А даёт возможность заглянуть в число Мерсенна по вопросу: из чего состоит, с помощью знания из чего состоит индекс числа Мерсенна.

ЗЫ. "Вот такие пироги с котятами". Мы тут не "плюшками балуемся".

Числа Мерсенна:
32767=2¹⁵-1=(2³-1)*4681=(2⁵-1)*1057=7*4681=31*1057, так как 15=3*5
...
134217727=2²⁷-1=(2³-1)*19173961=(2⁹-1)*262657=7*19173961=511*262657, так как 27=3*9
...
3435978367=2³⁵-1=(2⁵-1)*1108378657=(2⁷-1)*270549121=31*1108378657=127*270549121, так как 35=5*7
...
562949953421311=2⁴⁹-1=(2⁷-1)*1108378657=127*4432676798593, так как 49=7*7
...

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

Сначала разберёмся со следующим - Утверждением:

Если число n, где n=1,3,5, ... , составное, то есть n=ab, где a и b нечётные целые числа, то число Мерсенна 2^n -1 с индексом n составное и делится на числа Мерсенна с индексами a,b..

То есть 2^n -1 делится на 2^ a-1 и делится на 2^b -1

Нет, балуетесь

Мы тут не "плюшками балуемся".

2^ab -1 = (2^a)^b -1 = (разность b-тых степеней) = (разность а-тых степеней).
Извините, но это материал средней школы.

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

Значит с Утверждением проблем нет, оно не сложное. Интересны только М_р

Рекомендую скачать книгу

http://www.ams.org/publications/online-books/conm22-index

Factorizations of bn±1, b=2,3,5,6,7,10,11,12
Up to High Powers
Third Edition
by John Brillhart, D.H. Lehmer, J.L. Selfridge, Bryant Tuckerman,
and S.S. Wagstaff, Jr.

Михалыч, спасибо за книгу!

.
В соответствии с простым Утверждением – множество чисел Мерсенна обладает свойствами нечётных составных чисел натурального ряда. Тогда возникает возможность последовательного переноса решения состава числа на бесконечность с помощью процедуры:
1) n=ab
2) 2ⁿ-1= 2^ab-1=n₁=(2^a-1)(2^b-1)c
3) 2^n₁-1=n₂=(2^{2^a-1}-1)(2^{2^a-1}-1)(2^c-1)d
…….
Этот факт нам понадобится в дальнейшем