Мерсенн премьер

Мерсенн премьер

Назван в честь	Марин Мерсенн
Количество известных терминов	51
Предполагаемый нет. терминов	бесконечный
Последовательность ​	Числа Мерсенна
Первые сроки	3 , 7 , 31 , 127 , 8191
Самый большой известный термин	2 82,589,933 − 1 (7 декабря 2018 г.)
ОЭИС Индекс	А000668 Простые числа Мерсенна (формы 2^ p - 1, где p — простое число)

В математике простым числом Мерсенна называется простое число , которое на единицу меньше степени двойки . То есть это простое число вида M _n = 2 ^н − 1 для некоторого целого числа n . Они названы в честь Марина Мерсенна , французского монаха-минима , изучавшего их в начале 17 века. Если n — составное число , то и 2 тоже. ^н − 1 . Следовательно, эквивалентное определение простых чисел Мерсенна состоит в том, что это простые числа вида M _p = 2. ^п − 1 для некоторого простого числа p .

Показатели которые n, дают простые числа Мерсенна, равны 2, 3, 5, 7, 13, 17, 19, 31, ... (последовательность A000043 в OEIS ), а результирующие простые числа Мерсенна равны 3 , 7 , 31 , 127 , 8191, 131071, 524287, 2147483647 , ... (последовательность A000668 в OEIS ).

Числа вида M _n = 2 ^н − 1 без требования простоты можно назвать числами Мерсенна . Однако иногда числа Мерсенна определяются с дополнительным требованием, чтобы n было простым.Наименьшее составное число Мерсенна с простым показателем n равно 2. ¹¹ − 1 = 2047 = 23 × 89 .

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

По состоянию на 2023 год , известно 51 простое число Мерсенна. Самое большое известное простое число , 2 ^82,589,933 − 1 , является простым числом Мерсенна. С 1997 года все вновь найденные простые числа Мерсенна обнаруживаются в рамках Great Internet Mersenne Prime Search проекта распределенных вычислений . В декабре 2020 года была пройдена важная веха в проекте после того, как все показатели ниже 100 миллионов были проверены хотя бы один раз.

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

Нерешенная задача по математике :

Существует ли бесконечно много простых чисел Мерсенна?

(еще нерешенные задачи по математике)

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

Гипотеза Ленстры -Померанса-Вагстаффа утверждает, что существует бесконечно много простых чисел Мерсенна, и предсказывает порядок их роста и частоту: для каждого числа n в среднем должно быть около $e^{\gamma }\cdot \log _{2}(10)$ ≈ 5,92 простых чисел p с n десятичными цифрами (т.е. 10 ^n-1 < р < 10 ^н ) для чего $M_{p}$ является простым.

Также неизвестно, являются ли бесконечно многие числа Мерсенна с простыми показателями составными, хотя это следует из широко распространенных гипотез о простых числах, например, о бесконечности простых чисел Софи Жермен, конгруэнтных 3 ( mod 4 ). Для этих простых чисел p , 2 p + 1 (который также является простым) будет делить M _p , например, 23 | М ₁₁ , 47 | М ₂₃ , 167 | М ₈₃ , 263 | М ₁₃₁ , 359 | М ₁₇₉ , 383 | М ₁₉₁ , 479 | М ₂₃₉ и 503 | М ₂₅₁ (последовательность А002515 в OEIS ). Поскольку для этих простых чисел 2 p p + 1 конгруэнтно 7 по модулю 8, то 2 является квадратичным вычетом по модулю 2 p + 1 и мультипликативный порядок 2 по модулю 2 p + 1 должен делить ${\textstyle {\frac {(2p+1)-1}{2}}=p}$. Поскольку p — простое число, оно должно быть p или 1. Однако оно не может быть 1, поскольку $\Phi _{1}(2)=1$ и у 1 нет простых делителей , поэтому это должно быть p . Следовательно, 2 p + 1 делит $\Phi _{p}(2)=2^{p}-1$ и $2^{p}-1=M_{p}$ не может быть простым.Первые четыре простых числа Мерсенна — это M ₂ = 3 , M ₃ = 7 , M ₅ = 31 и M ₇ = 127 , а поскольку первое простое число Мерсенна начинается с M ₂ , все простые числа Мерсенна конгруэнтны 3 (по модулю 4). Кроме M ₀ = 0 и M ₁ = 1 , все остальные числа Мерсенна также конгруэнтны 3 (по модулю 4). Следовательно, в простой факторизации числа Мерсенна ( ≥ M ₂ ) должен быть хотя бы один простой множитель, конгруэнтный 3 (mod 4).

Основная теорема о числах Мерсенна гласит, что если M _p простое число, то показатель степени p также должен быть простым. Это следует из тождества $${\begin{aligned}2^{ab}-1&=(2^{a}-1)\cdot \left(1+2^{a}+2^{2a}+2^{3a}+\cdots +2^{(b-1)a}\right)\\&=(2^{b}-1)\cdot \left(1+2^{b}+2^{2b}+2^{3b}+\cdots +2^{(a-1)b}\right).\end{aligned}}$$Это исключает простоту чисел Мерсенна с составным показателем, например M ₄ = 2. ⁴ − 1 = 15 = 3 × 5 = (2 ² − 1) × (1 + 2 ² ) .

Хотя приведенные выше примеры могут предполагать, что M _p является простым для всех простых чисел p , это не так, и наименьшим контрпримером является число Мерсенна.

М ₁₁ = 2 ¹¹ − 1 = 2047 = 23 × 89 .

Имеющиеся данные свидетельствуют о том, что случайно выбранное число Мерсенна с гораздо большей вероятностью окажется простым, чем произвольно выбранное нечетное целое число аналогичного размера. Тем не менее, простые значения M _p , по-видимому, становятся все более редкими по мере увеличения p . Например, восемь из первых 11 простых чисел p порождают простое число Мерсенна M _p (правильные термины в исходном списке Мерсенна), в то время как M _p является простым только для 43 из первых двух миллионов простых чисел (до 32 452 843).

Отсутствие в настоящее время какого-либо простого теста, позволяющего определить, является ли данное число Мерсенна простым, делает поиск простых чисел Мерсенна сложной задачей, поскольку числа Мерсенна растут очень быстро. Тест Лукаса-Лемера на простоту (LLT) — это эффективный тест на простоту , который значительно облегчает эту задачу, значительно упрощая проверку простоты чисел Мерсенна, чем проверку простоты большинства других чисел того же размера. Поиски самого большого из известных простых чисел стали своего рода культом . Следовательно, на поиск новых простых чисел Мерсенна было затрачено большое количество компьютерных мощностей, большая часть которых сейчас выполняется с использованием распределенных вычислений .

Арифметика по модулю числа Мерсенна особенно эффективна на двоичном компьютере , что делает их популярным выбором, когда требуется простой модуль, например, генератор случайных чисел Парка-Миллера . Чтобы найти примитивный многочлен числового порядка Мерсенна, необходимо знать факторизацию этого числа, поэтому простые числа Мерсенна позволяют находить примитивные многочлены очень высокого порядка. Такие примитивные трехчлены используются в генераторах псевдослучайных чисел с очень большими периодами, таких как твистер Мерсенна , обобщенный сдвиговый регистр и генераторы Фибоначчи с запаздыванием .

Совершенные числа

Основная статья: теорема Евклида – Эйлера

числа Мерсенна Mp _{Простые} тесно связаны с совершенными числами . В IV веке до нашей эры Евклид доказал, что если 2 ^п − 1 простое, тогда 2 ^{п - 1} (2 ^п − 1 ) — совершенное число. В 18 веке Леонард Эйлер доказал, что, наоборот, все даже совершенные числа имеют такой вид. Это известно как теорема Евклида-Эйлера . Неизвестно, существуют ли нечетные совершенные числа .

Альтернативная форма Perfect Numbers (не затрагивающая сути): Если $(M=2^{n}-1)$ является простым числом, то $P=M(M+1)/2$ является совершенным числом. (Совершенные числа — это треугольные числа, основанием которых является простое число Мерсенна.)

История

2	3	5	7	11	13	17	19
23	29	31	37	41	43	47	53
59	61	67	71	73	79	83	89
97	101	103	107	109	113	127	131
137	139	149	151	157	163	167	173
179	181	191	193	197	199	211	223
227	229	233	239	241	251	257	263
269	271	277	281	283	293	307	311
Первые 64 показателя простых чисел, соответствующие простым числам Мерсенна, выделены голубым и жирным шрифтом, а те, которые, по мнению Мерсенна, это были, выделены красным и жирным шрифтом.

17-го века Простые числа Мерсенна получили свое название от французского ученого Марина Мерсенна , который составил список простых чисел Мерсенна с показателями до 257. Показатели степени, перечисленные Мерсенном в 1644 году, были следующими:

2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.

Его список повторял известные простые числа того времени с показателями до 19. Его следующая запись, 31, была правильной, но затем список стал в значительной степени неправильным, поскольку Мерсенн по ошибке включил M ₆₇ и M ₂₅₇ (которые являются составными) и опустил M _61. , M ₈₉ и M ₁₀₇ (простые). Мерсенн мало рассказал о том, как он составил свой список.

Эдуард Лукас доказал в 1876 году, что M ₁₂₇ действительно является простым, как утверждал Мерсенн. Это было самое большое известное простое число за 75 лет до 1951 года, когда Ферье нашел большее простое число: $(2^{148}+1)/17$с помощью настольной счетной машины. М ₆₁ было определено как простое в 1883 году Иваном Михеевичем Первушиным , хотя Мерсенн утверждал, что оно составное, и по этой причине его иногда называют числом Первушина. Это было второе по величине известное простое число, и оно оставалось таковым до 1911 года. Лукас обнаружил еще одну ошибку в списке Мерсенна в 1876 году, продемонстрировав, что M ₆₇ является составным, не найдя множителя. Никакого фактора не было обнаружено до знаменитого выступления Фрэнка Нельсона Коула в 1903 году. Не говоря ни слова, он подошел к доске и возвел 2 в 67-ю степень, затем вычел единицу, в результате чего получилось число 147 573 952 589 676 412 927 . На другой стороне доски он умножил 193 707 721 × 761 838 257 287 и получил то же число, а затем молча вернулся на свое место (под аплодисменты). Позже он сказал, что на поиск результата у него ушло «три года воскресений». Правильный список всех простых чисел Мерсенна в этом диапазоне чисел был завершен и тщательно проверен только примерно через три столетия после того, как Мерсенн опубликовал свой список.

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

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

Первые четыре простых числа Мерсенна М ₂ = 3 , М ₃ = 7 , М ₅ = 31 и М ₇ = 127 были известны еще в древности. Пятый, М ₁₃ = 8191 , был открыт анонимно до 1461 г.; следующие два ( M ₁₇ и M ₁₉ ) были найдены Пьетро Катальди в 1588 году. Спустя почти два столетия M ₃₁ в 1772 году подтвердил, что Леонард Эйлер является простым . Следующим (в историческом, а не числовом порядке) было M ₁₂₇ , найден Эдуардом Лукасом в 1876 году, затем М ₆₁ Иваном Михеевичем Первушиным в 1883 году. Еще два ( М ₈₉ и М ₁₀₇ ) были найдены в начале 20 века Р. Э. Пауэрсом в 1911 и 1914 годах соответственно.

В настоящее время наиболее эффективным методом проверки простоты чисел Мерсенна является тест на простоту Лукаса-Лемера . В частности, можно показать, что для простых p > 2 M p ₌ 2 ^п − 1 является простым тогда и только тогда, когда M _p делит S _{p − 2} , где S ₀ = 4 и S _k = ( S _{k − 1} ) ² − 2 для k > 0 .

В эпоху ручных вычислений все показатели степени до 257 включительно были проверены с помощью теста Лукаса-Лемера и оказались составными. Заметный вклад внес профессор физики Йельского университета на пенсии Гораций Скаддер Улер, который выполнил расчеты для показателей 157, 167, 193, 199, 227 и 229. К несчастью для этих исследователей, интервал, который они тестировали, содержит самый большой известный относительный разрыв между простыми числами Мерсенна: следующий показатель степени простых чисел Мерсенна, 521, окажется более чем в четыре раза больше предыдущего рекорда 127.

График количества цифр крупнейшего известного простого числа Мерсенна по годам - ​​электронная эра. Вертикальная шкала является логарифмической по количеству цифр и, таким образом, представляет собой $\log(\log(y))$ функция по значению простого числа.

Поиск простых чисел Мерсенна произвел революцию с появлением электронного цифрового компьютера. Алан Тьюринг искал их на Манчестерском корабле «Марк-1» в 1949 году. но первая успешная идентификация простого числа Мерсенна, M ₅₂₁ , была достигнута с помощью этого средства в 22:00 30 января 1952 года с использованием Западного автоматического компьютера Национального бюро стандартов США (SWAC) в Институте численного анализа в Калифорнийский университет в Лос-Анджелесе под руководством Д. Х. Лемера с компьютерной поисковой программой, написанной и управляемой профессором Р. М. Робинсоном . Это было первое простое число Мерсенна, идентифицированное за тридцать восемь лет; следующий, M ₆₀₇ , был найден компьютером чуть менее чем через два часа. Еще три — M ₁₂₇₉ , M ₂₂₀₃ и M ₂₂₈₁ — были найдены той же программой в течение следующих нескольких месяцев. М ₄₄₂₃ было первым обнаруженным простым числом, содержащим более 1000 цифр, М _{44 497} было первым, содержащим более 10 000, а М _{6 972 593} было первым простым числом, превышающим миллион. В общем, количество цифр в десятичном представлении M _n равно ⌊ n × log ₁₀ 2⌋ + 1 , где ⌊ x ⌋ обозначает функцию пола (или, что то же самое, ⌊log ₁₀ M _n ⌋ + 1 ).

В сентябре 2008 года математики Калифорнийского университета в Лос-Анджелесе, участвовавшие в Великом поиске простых чисел Мерсенна в Интернете (GIMPS), выиграли часть приза в размере 100 000 долларов от Electronic Frontier Foundation за открытие простого числа Мерсенна, состоящего почти из 13 миллионов цифр. Приз, окончательно подтвержденный в октябре 2009 года, присуждается за первое известное простое число, содержащее не менее 10 миллионов цифр. Простое число было обнаружено на Dell OptiPlex 745 23 августа 2008 года. Это было восьмое простое число Мерсенна, обнаруженное в Калифорнийском университете в Лос-Анджелесе.

12 апреля 2009 г. журнал сервера GIMPS сообщил, что, возможно, было найдено 47-е простое число Мерсенна. Находка была впервые замечена 4 июня 2009 года и подтверждена неделю спустя. Простое число равно 2 ^42,643,801 − 1 . Хотя в хронологическом порядке это 47-е открытое простое число Мерсенна, оно меньше самого большого из известных на тот момент 45-го открытого числа.

25 января 2013 года Кертис Купер , математик из Университета Центрального Миссури , открыл 48-е простое число Мерсенна, 2 ^57,885,161 − 1 (число из 17 425 170 цифр) в результате поиска, выполненного сетью серверов GIMPS.

19 января 2016 года Купер опубликовал свое открытие 49-го простого числа Мерсенна, 2 ^74,207,281 − 1 (число из 22 338 618 цифр) в результате поиска, выполненного сетью серверов GIMPS. Это было четвертое простое число Мерсенна, открытое Купером и его командой за последние десять лет.

2 сентября 2016 года Великий Интернет-поиск простых чисел Мерсенна завершил проверку всех тестов ниже M _{37 156 667} , тем самым официально подтвердив свою позицию 45-го простого числа Мерсенна.

3 января 2018 года было объявлено, что Джонатан Пейс, 51-летний инженер-электрик, живущий в Джермантауне, штат Теннесси , нашел 50-е простое число Мерсенна, 2 ^77,232,917 − 1 (число из 23 249 425 цифр) в результате поиска, выполненного сетью серверов GIMPS. Открытие было сделано с помощью компьютера в офисе церкви в том же городе.

21 декабря 2018 года было объявлено, что программа Great Internet Mersenne Prime Search (GIMPS) обнаружила самое большое известное простое число — 2. ^82,589,933 − 1 , имеющий 24 862 048 цифр. Компьютер, добровольно предоставленный Патриком Ларошем из Окалы, Флорида, сделал находку 7 декабря 2018 года.

В конце 2020 года GIMPS начал использовать новую методику исключения потенциальных простых чисел Мерсенна, называемую тестом вероятного простого числа (PRP), основанную на разработке Роберта Гербича в 2017 году, и простой способ проверки тестов, разработанный Кшиштофом Петшаком в 2018 году. низкий уровень ошибок и простота доказательства, это почти вдвое сократило время вычислений, чтобы исключить потенциальные простые числа по тесту Лукаса-Лемера (поскольку двум пользователям больше не нужно было бы выполнять один и тот же тест для подтверждения результата другого), хотя показатели степени, проходящие тест PRP-тест по-прежнему требует подтверждения их первичности.

Теоремы о числах Мерсенна

Числа Мерсенна — 0, 1, 3, 7, 15, 31, 63, ... (последовательность A000225 в OEIS ).

1. Если a и p — натуральные числа такие, что a ^п − 1 простое число, тогда a = 2 или p = 1 .
   • Доказательство : а ≡ 1 ( mod a - 1) . Тогда ​ ^п ≡ 1 (mod a − 1) , поэтому a ^п - 1 ≡ 0 (мод а - 1) . Таким образом, а − 1 | а ^п − 1 . не менее, Тем ^п − 1 простое число, поэтому a − 1 = a ^п - 1 или а - 1 знак равно ±1 . В первом случае а = а ^п , следовательно, a = 0, 1 (что является противоречием, поскольку ни −1, ни 0 не являются простыми числами) или p = 1. В последнем случае a = 2 или a = 0 . Однако если a = 0 , 0 ^п − 1 = 0 − 1 = −1, что не является простым. Следовательно, а = 2 .
2. Если 2 ^п − 1 простое число, тогда p простое число.
   • Доказательство : предположим, что p составное, поэтому можно записать p = ab с a и b > 1 . Тогда 2 ^п − 1 = 2 ^аб − 1 = (2 ^а ) ^б − 1 = (2 ^а − 1) ( (2 ^а ) ^{б -1} + (2 ^а ) ^{б -2} + ... + 2 ^а + 1 ) итак 2 ^п − 1 является составным. В противоположность этому, если 2 ^п − 1 простое число, тогда p простое число.
3. Если p — нечетное простое число, то каждое простое число q , делящее 2 ^п − 1 должно быть 1 плюс кратное 2 p . Это справедливо даже тогда, когда 2 ^п − 1 — простое число.
   • Например, 2 ⁵ − 1 = 31 — простое число, а 31 = 1 + 3 × (2 × 5) . Составной пример — 2 ¹¹ − 1 = 23 × 89 , где 23 = 1 + (2 × 11) и 89 = 1 + 4 × (2 × 11) .
   • Доказательство : По малой теореме Ферма . q увеличивается в 2 раза ^{q -1} − 1 . Поскольку q кратно 2 ^п − 1 , для всех положительных целых чисел c , q также является фактором 2 ^ПК − 1 . Поскольку p простое число и q не кратен 2 ¹ − 1 , p также является наименьшим положительным целым числом x таким, что q кратно 2 ^х − 1 . В результате для всех натуральных чисел x , q увеличивается в 2 раза. ^х − 1 тогда и только тогда, когда p является фактором x . Следовательно, поскольку q в 2 раза ^{q -1} - 1 , p является фактором q - 1, поэтому q ≡ 1 (mod p ) . Кроме того, поскольку q в 2 раза ^п − 1 , что нечетно, q нечетно. Следовательно, q ≡ 1 (mod 2 p ) .
   • Этот факт приводит к доказательству теоремы Евклида , утверждающей бесконечность простых чисел, отличному от доказательства, написанного Евклидом: для каждого нечетного простого числа p все простые числа, делящие 2 ^п − 1 больше, чем p ; таким образом, всегда существуют простые числа большего размера, чем любое конкретное простое число.
   • Из этого факта следует, что для каждого простого числа p > 2 число вида 2kp , +1 меньшее или равное Mp _k , для некоторого целого числа . существует хотя бы одно простое
4. Если p — нечетное простое число, то каждое простое число q , делящее 2 ^п − 1 конгруэнтно ±1 (по модулю 8) .
   • Доказательство : 2 ^{р +1} ≡ 2 (mod q ) , поэтому 2 ^{⁠ 1 / 2 ⁠ (р+1)} является квадратным корнем из 2 по модулю q . По квадратичной взаимности каждый простой модуль, в котором число 2 имеет квадратный корень, конгруэнтен ±1 (по модулю 8) .
5. Простое число Мерсенна не может быть простым числом Вифериха .
   • Доказательство : мы покажем, что если p = 2 ^м − 1 — простое число Мерсенна, то сравнение 2 ^{р -1} ≡ 1 (против p ² ) не держится. По малой теореме Ферма m | п - 1 . Следовательно, можно написать p − 1 = mλ . Если данное сравнение выполнено, то p ² | 2 ^mλ − 1 , следовательно, 0 ≡ ⁠ 2 ^mλ − 1 / 2 ^м − 1 ⁠ = 1 + 2 ^м + 2 ^22м + ... + 2 ^{( λ − 1) м} ≡ λ mod (2 ^м − 1) . Следовательно, р | λ и, следовательно, −1 = 0 (mod p), что невозможно.
6. Если m и n — натуральные числа, то m и n тогда взаимно просты и только тогда, когда 2 ^м − 1 и 2 ^н − 1 взаимно просты. Следовательно, простое число делит не более одного числа Мерсенна в простой степени. То есть набор пагубных чисел Мерсенна попарно взаимно прост.
7. Если p и 2 p + 1 оба простые (это означает, что p — простое число Софи Жермен ), и p конгруэнтно ( по 3 модулю 4) , то 2 p + 1 делит 2 ^п − 1 .
   • Пример : 11 и 23 — простые числа, а 11 = 2 × 4 + 3 , поэтому 23 делит 2. ¹¹ − 1 .
   • Доказательство : Пусть q равно 2p 1 + . По малой теореме Ферма 2 ^{2 р} ≡ 1 (mod q ) , поэтому либо 2 ^п ≡ 1 (по модулю q ) или 2 ^п ≡ -1 (мод q ) . Предположим, что последнее верно, тогда 2 ^{р +1} = (2 ^{⁠ 1/2 ⁠ + ( ) р 1} ) ² ≡ −2 (mod q ) , поэтому −2 будет квадратичным вычетом по модулю q . Однако, поскольку p конгруэнтно 3 (по модулю 4) , q конгруэнтно 7 (по модулю 8) , и, следовательно, 2 является квадратичным вычетом по модулю q . Кроме того, поскольку q конгруэнтно 3 (mod 4) , −1 является квадратичным невычетом по модулю q , поэтому −2 является произведением вычета и невычета и, следовательно, является невычетом, что является противоречием. Следовательно, первое сравнение должно быть верным и 2 p + 1 делит M _p .
8. Все составные делители чисел Мерсенна с простым показателем являются сильными псевдопростыми числами по основанию 2.
9. За исключением 1, число Мерсенна не может быть полной степенью. То есть и в соответствии с теоремой Михайлеску уравнение 2 ^м − 1 = п ^к не имеет решений, где m , n и k — целые числа с m > 1 и k > 1 .
10. Числовая последовательность Мерсенна является членом семейства последовательностей Люка . Это U _n (3, 2). То есть число Мерсенна m _n = 3 m _{n -1} - 2 m _{n -2} при m ₀ = 0 и m ₁ = 1 .

Список известных простых чисел Мерсенна

Основная статья: Список простых чисел Мерсенна и совершенных чисел

По состоянию на 2023 год , 51 известное простое число Мерсенна равно 2 ^п − 1 для следующих p :

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 2170, 1, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 209960 11, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933. (последовательность A000043 в OEIS )

Факторизация составных чисел Мерсенна

Поскольку простые числа Мерсенна делятся только на 1 и на себя. Однако не все числа Мерсенна являются простыми числами Мерсенна. Числа Мерсенна являются очень хорошими тестовыми примерами для алгоритма сита специального числового поля , поэтому часто самым большим числом, факторизованным с помощью этого алгоритма, было число Мерсенна. По состоянию на июнь 2019 г. , 2 ^1,193 − 1 – рекордсмен, будучи факторизованным с помощью варианта специального сита числового поля, которое позволяет факторизовать несколько чисел одновременно. См. записи целочисленной факторизации для получения ссылок на дополнительную информацию. Специальное сито числового поля может факторизовать числа с более чем одним большим фактором. Если число имеет только один очень большой фактор, то другие алгоритмы могут факторизовать большие числа, сначала находя малые факторы, а затем выполняя тест на простоту кофактора. По состоянию на сентябрь 2022 г. , наибольшее полностью факторизованное число (с допустимыми простыми множителями) равно 2 ^12,720,787 − 1 = 1 119 429 257 × 175 573 124 547 437 977 × 8 480 999 878 421 106 991 × q , где q — вероятное простое число из 3 829 294 цифр. Его обнаружил участник GIMPS под ником «Funky Waddle». По состоянию на сентябрь 2022 г. , число Мерсенна M ₁₂₇₇ — наименьшее составное число Мерсенна, коэффициенты которого неизвестны; у него нет простых делителей ниже 2 ⁶⁸ , и очень маловероятно, что коэффициенты будут ниже 10. ⁶⁵ (~2 ²¹⁶ ).

В таблице ниже показаны факторизации первых 20 составных чисел Мерсенна (последовательность A244453 в OEIS ).

п	М п	Факторизация M p
11	2047	23 × 89
23	8388607	47 × 178,481
29	536870911	233 × 1,103 × 2,089
37	137438953471	223 × 616,318,177
41	2199023255551	13,367 × 164,511,353
43	8796093022207	431 × 9,719 × 2,099,863
47	140737488355327	2,351 × 4,513 × 13,264,529
53	9007199254740991	6,361 × 69,431 × 20,394,401
59	576460752303423487	179 951 × 3 203 431 780 337 (13 цифр)
67	147573952589676412927	193 707 721 × 761 838 257 287 (12 цифр)
71	2361183241434822606847	228,479 × 48,544,121 × 212,885,833
73	9444732965739290427391	439 × 2 298 041 × 9 361 973 132 609 (13 цифр)
79	604462909807314587353087	2687 × 202029703 × 1113491139767 (13 цифр)
83	967140655691...033397649407	167 × 57 912 614 113 275 649 087 721 (23 цифры)
97	158456325028...187087900671	11 447 × 13 842 607 235 828 485 645 766 393 (26 цифр)
101	253530120045...993406410751	7 432 339 208 719 (13 цифр) × 341 117 531 003 194 129 (18 цифр)
103	101412048018...973625643007	2 550 183 799 × 3 976 656 429 941 438 590 393 (22 цифры)
109	649037107316...312041152511	745 988 807 × 870 035 986 098 720 987 332 873 (24 цифры)
113	103845937170...992658440191	3391 × 23279 × 65993 × 1868569 × 1066818132868207 (16 цифр)
131	272225893536...454145691647	263 × 10 350 794 431 055 162 386 718 619 237 468 234 569 (38 цифр)

Количество факторов для первых 500 чисел Мерсенна можно найти по адресу (последовательность A046800 в OEIS ).

Числа Мерсенна в природе и других местах.

В математической задаче « Ханойская башня » решение головоломки с башней из n дисков требует M _n шагов, при условии, что ошибок не допущено. Число рисовых зерен на всей шахматной доске в задаче «Пшеница и шахматная доска» равно M ₆₄ .

Астероид , с номером малой планеты 8191 назван 8191 Мерсенн в честь Марина Мерсенна, потому что 8191 является простым числом Мерсенна ( 3 Юноны , 7 Ириды 31 Евфросины и 127 Иоганна были открыты и названы в 19 веке).

В геометрии целочисленный прямоугольный треугольник , который является примитивным и имеет четную сторону, степень 2 ( ≥ 4 ), порождает уникальный прямоугольный треугольник, такой, что его внутренний радиус всегда является числом Мерсенна. Например, если четный катет равен 2 ^{п + 1} затем, поскольку он примитивен, он ограничивает нечетную часть равным 4 ^н − 1 , гипотенуза равна 4 ^н + 1 , а его радиус равен 2. ^н  − 1 .

Бонусы Мерсенна-Ферма

Число Мерсенна – Ферма определяется как ⁠ 2 ^{п р} − 1 / 2 ^{п р - 1} − 1 ⁠ с простым p , r натуральным числом и может быть записано как MF( p , r ) . Когда r = 1 , это число Мерсенна. Когда p = 2 , это число Ферма . Единственные известные простые числа Мерсенна – Ферма с r > 1 :

МФ(2, 2), МФ(2, 3), МФ(2, 4), МФ(2, 5), МФ(3, 2), МФ(3, 3), МФ(7, 2) и МФ(59, 2) .

В самом деле, MF( p , r ) = Φ _{p ^р} (2) , где Φ – круговой многочлен .

Обобщения

Основная статья: Обобщенное простое число Мерсенна

Простейшими обобщенными простыми числами Мерсенна являются простые числа вида f (2 ^н ) , где f ( x ) низкой степени — многочлен с малыми целыми коэффициентами . Пример: 2 ⁶⁴ − 2 ³² + 1 , в данном случае n = 32 и f ( x ) = x ² − Икс + 1 ; другой пример - 2 ¹⁹² − 2 ⁶⁴ − 1 , в данном случае n = 64 и f ( x ) = x ³ - Икс - 1 .

Также естественно попытаться обобщить простые числа вида 2 ^н − 1 к простым числам вида b ^н − 1 (при b ≠ 2 и n > 1 ). Однако (см. также теоремы выше ), b ^н − 1 всегда делится на b − 1 , поэтому, если последнее не является единицей , первое не является простым числом. Это можно исправить, разрешив b быть алгебраическим целым числом вместо целого числа:

Комплексные числа

В кольце целых чисел ( действительных чисел ), если b − 1 — единица , то b равно либо 2, либо 0. Но 2 ^н − 1 — обычные простые числа Мерсенна, а формула 0 ^н −1 не приводит ни к чему интересному (поскольку оно всегда равно −1 для всех n > 0 ). Таким образом, мы можем рассматривать кольцо «целых» комплексных чисел вместо действительных чисел , таких как целые числа Гаусса и целые числа Эйзенштейна .

Гауссовы простые числа Мерсенна

Если мы рассмотрим кольцо гауссовских целых чисел , мы получим случай b = 1 + i и b = 1 − i , и можем спросить ( WLOG ), для которого n число (1 + i ) ^н − 1 — гауссово простое число , которое затем будем называть гауссовым простым числом Мерсенна .

(1 + я ) ^н − 1 является гауссовым простым числом для следующих n :

2, 3, 5, 7, 11, 19, 29, 47, 73, 79, 113, 151, 157, 163, 167, 239, 241, 283, 353, 367, 379, 457, 997, 1367, 3041, 10141, 14699, 27529, 49207, 77291, 85237, 106693, 160423, 203789, 364289, 991961, 1203793, 1667321, 3704053, 4792057,... A057429 в OEIS )

Подобно последовательности показателей обычных простых чисел Мерсенна, эта последовательность содержит только (рациональные) простые числа.

Что касается всех гауссовских простых чисел, нормы (то есть квадраты абсолютных значений) этих чисел являются рациональными простыми числами:

5, 13, 41, 113, 2113, 525313, 536903681, 140737471578113, ... (последовательность A182300 в OEIS ).

Простые числа Эйзенштейна Мерсенна

Можно встретить случаи, когда такое простое число Мерсенна также является простым числом Эйзенштейна , имея вид b = 1 + ω и b = 1 − ω . В этих случаях такие числа называются простыми числами Эйзенштейна-Мерсенна .

(1 + ω ) ^н − 1 является простым числом Эйзенштейна для следующих n :

2, 5, 7, 11, 17, 19, 79, 163, 193, 239, 317, 353, 659, 709, 1049, 1103, 1759, 2029, 5153, 7541, 9049, 10453, 23743, 255361 , 534827, 2237561, ... (последовательность A066408 в OEIS )

Нормы (то есть квадраты абсолютных значений) этих простых чисел Эйзенштейна являются рациональными простыми числами:

7, 271, 2269, 176419, 129159847, 1162320517, ... (последовательность A066413 в OEIS )

Разделить целое число

Восстановить простые числа

Основная статья: Репунит

Другой способ справиться с тем фактом, что b ^н − 1 всегда делится на b − 1 , нужно просто вынуть этот множитель и спросить, какие значения n составляют

${\frac {b^{n}-1}{b-1}}$

быть главным. (Целое число b может быть как положительным, так и отрицательным.) Если, например, мы возьмем b = 10 , мы получим n значений:

2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, ... (последовательность A004023 в OEIS ),
соответствующие простым числам 11, 1111111111111111111, 11111111111111111111111, ... (последовательность A004022 в OEIS ).

Эти простые числа называются простыми числами повторения. Другой пример: когда мы берем b = −12 , мы получаем n значений:

2, 5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, ... (последовательность A057178 в OEIS ),
соответствующие простым числам -11, 19141, 57154490053, ....

Это гипотеза о том, что для каждого целого числа b, не являющегося полной степенью , существует бесконечно много значений n таких, что ⁠ b ^н − 1 / b − 1 ⁠ простое число. (Когда b — идеальная степень, можно показать, что существует не более одного n такого, что значения ⁠ b ^н − 1 / b − 1 ⁠ простое)

Наименьшее n такое, что ⁠ b ^н − 1 / b − 1 ⁠ простое число (начиная с b = 2 , 0, если такого n не существует)

2, 3, 2, 3, 2, 5, 3, 0, 2, 17, 2, 5, 3, 3, 2, 3, 2, 19, 3, 3, 2, 5, 3, 0, 7, 3, 2, 5, 2, 7, 0, 3, 13, 313, 2, 13, 3, 349, 2, 3, 2, 5, 5, 19, 2, 127, 19, 0, 3, 4229, 2, 11, 3, 17, 7, 3, 2, 3, 2, 7, 3, 5, 0, 19, 2, 19, 5, 3, 2, 3, 2, ... (последовательность A084740 в ОЭИС )

Для отрицательных оснований b это (начиная с b = −2 , 0 , если такого n не существует)

3, 2, 2, 5, 2, 3, 2, 3, 5, 5, 2, 3, 2, 3, 3, 7, 2, 17, 2, 3, 3, 11, 2, 3, 11, 0, 3, 7, 2, 109, 2, 5, 3, 11, 31, 5, 2, 3, 53, 17, 2, 5, 2, 103, 7, 5, 2, 7, 1153, 3, 7, 21943, 2, 3, 37, 53, 3, 17, 2, 7, 2, 3, 0, 19, 7, 3, 2, 11, 3, 5, 2, ... (последовательность A084742 в OEIS ) (обратите внимание, что эта последовательность OEIS не допускает n = 2 )

Наименьшее основание b такое, что ⁠ b ^{простое( п )} − 1 / b − 1 ⁠ простое число, являются

2, 2, 2, 2, 5, 2, 2, 2, 10, 6, 2, 61, 14, 15, 5, 24, 19, 2, 46, 3, 11, 22, 41, 2, 12, 22, 3, 2, 12, 86, 2, 7, 13, 11, 5, 29, 56, 30, 44, 60, 304, 5, 74, 118, 33, 156, 46, 183, 72, 606, 602, 223, 115, 37, 52, 104, 41, 6, 338, 217, ... (последовательность A066180 в OEIS )

Для отрицательных оснований b они равны

3, 2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (последовательность A103795 в OEIS )

Другие обобщенные простые числа Мерсенна

Другое обобщенное число Мерсенна:

${\frac {a^{n}-b^{n}}{a-b}}$

с a , b любыми взаимно простыми целыми числами, a > 1 и − a < b < a . ( Поскольку ^н − б ^н всегда делится на a − b , деление необходимо, чтобы была возможность найти простые числа.) Мы можем спросить, какое n делает это число простым. Можно показать, что такое n должно быть простым числом или равняться 4, а n может быть равно 4 тогда и только тогда, когда a + b = 1 и a ² + б ² является простым. Это гипотеза, что для любой пары ( a , b ), такой что a и b не являются одновременно совершенными r -ми степенями для любого r и −4 ab не является идеальной четвертой степенью , существует бесконечно много значений n таких, что ⁠ a ^н − б ^н / a − b ⁠ простое число. Однако это не было доказано ни для одного значения ( a , b ) .

Для получения дополнительной информации см.

а	б	цифры такой , что ⁠ a н − б н / a − b ⁠ простое число (некоторые большие термины являются лишь вероятными простыми числами , эти n проверены до 100000 за | б | ≤ 5 или | б | знак равно а - 1 , 20000 за 5 < | б | < а - 1 )	OEIS Последовательность
2	1	2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, ..., 74207281, ..., 77232917, ..., 82589933, ...	А000043
2	−1	3, 4 * , 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, ..., 13347311, 13372531, ...	А000978
3	2	2, 3, 5, 17, 29, 31, 53, 59, 101, 277, 647, 1061, 2381, 2833, 3613, 3853, 3929, 5297, 7417, 90217, 122219, 173191, 256199, 336353, 485977, 591827, 1059503, ...	А057468
3	1	3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177, 9011, 9551, 36913, 43063, 49681, 57917, 483611, 877843, ...	А028491
3	−1	2 * , 3, 5, 7, 13, 23, 43, 281, 359, 487, 577, 1579, 1663, 1741, 3191, 9209, 11257, 12743, 13093, 17027, 26633, 104243, 134227, 152287, 700897, 1205459, ...	А007658
3	−2	3, 4 * , 7, 11, 83, 149, 223, 599, 647, 1373, 8423, 149497, 388897, ...	А057469
4	3	2, 3, 7, 17, 59, 283, 311, 383, 499, 521, 541, 599, 1193, 1993, 2671, 7547, 24019, 46301, 48121, 68597, 91283, 131497, 148663, 184463, 341233, ...	А059801
4	1	2 (других нет)
4	−1	2 * , 3 (других нет)
4	−3	3, 5, 19, 37, 173, 211, 227, 619, 977, 1237, 2437, 5741, 13463, 23929, 81223, 121271, ...	А128066
5	4	3, 43, 59, 191, 223, 349, 563, 709, 743, 1663, 5471, 17707, 19609, 35449, 36697, 45259, 91493, 246497, 265007, 289937, ...	А059802
5	3	13, 19, 23, 31, 47, 127, 223, 281, 2083, 5281, 7411, 7433, 19051, 27239, 35863, 70327, ...	А121877
5	2	2, 5, 7, 13, 19, 37, 59, 67, 79, 307, 331, 599, 1301, 12263, 12589, 18443, 20149, 27983, ...	А082182
5	1	3, 7, 11, 13, 47, 127, 149, 181, 619, 929, 3407, 10949, 13241, 13873, 16519, 201359, 396413, 1888279, ...	А004061
5	−1	5, 67, 101, 103, 229, 347, 4013, 23297, 30133, 177337, 193939, 266863, 277183, 335429, ...	А057171
5	−2	2 * , 3, 17, 19, 47, 101, 1709, 2539, 5591, 6037, 8011, 19373, 26489, 27427, ...	А082387
5	−3	2 * , 3, 5, 7, 17, 19, 109, 509, 661, 709, 1231, 12889, 13043, 26723, 43963, 44789, ...	А122853
5	−4	4 * , 5, 7, 19, 29, 61, 137, 883, 1381, 1823, 5227, 25561, 29537, 300893, ...	А128335
6	5	2, 5, 11, 13, 23, 61, 83, 421, 1039, 1511, 31237, 60413, 113177, 135647, 258413, ...	А062572
6	1	2, 3, 7, 29, 71, 127, 271, 509, 1049, 6389, 6883, 10613, 19889, 79987, 608099, ...	А004062
6	−1	2 * , 3, 11, 31, 43, 47, 59, 107, 811, 2819, 4817, 9601, 33581, 38447, 41341, 131891, 196337, ...	А057172
6	−5	3, 4 * , 5, 17, 397, 409, 643, 1783, 2617, 4583, 8783, ...	А128336
7	6	2, 3, 7, 29, 41, 67, 1327, 1399, 2027, 69371, 86689, 355039, ...	А062573
7	5	3, 5, 7, 113, 397, 577, 7573, 14561, 58543, ...	А128344
7	4	2, 5, 11, 61, 619, 2879, 2957, 24371, 69247, ...	А213073
7	3	3, 7, 19, 109, 131, 607, 863, 2917, 5923, 12421, ...	А128024
7	2	3, 7, 19, 79, 431, 1373, 1801, 2897, 46997, ...	А215487
7	1	5, 13, 131, 149, 1699, 14221, 35201, 126037, 371669, 1264699, ...	А004063
7	−1	3, 17, 23, 29, 47, 61, 1619, 18251, 106187, 201653, ...	А057173
7	−2	2 * , 5, 23, 73, 101, 401, 419, 457, 811, 1163, 1511, 8011, ...	А125955
7	−3	3, 13, 31, 313, 3709, 7933, 14797, 30689, 38333, ...	А128067
7	−4	2 * , 3, 5, 19, 41, 47, 8231, 33931, 43781, 50833, 53719, 67211, ...	А218373
7	−5	2 * , 11, 31, 173, 271, 547, 1823, 2111, 5519, 7793, 22963, 41077, 49739, ...	А128337
7	−6	3, 53, 83, 487, 743, ...	А187805
8	7	7, 11, 17, 29, 31, 79, 113, 131, 139, 4357, 44029, 76213, 83663, 173687, 336419, 615997, ...	А062574
8	5	2, 19, 1021, 5077, 34031, 46099, 65707, ...	А128345
8	3	2, 3, 7, 19, 31, 67, 89, 9227, 43891, ...	А128025
8	1	3 (других нет)
8	−1	2 * (никаких других)
8	−3	2 * , 5, 163, 191, 229, 271, 733, 21059, 25237, ...	А128068
8	−5	2 * , 7, 19, 167, 173, 223, 281, 21647, ...	А128338
8	−7	4 * , 7, 13, 31, 43, 269, 353, 383, 619, 829, 877, 4957, 5711, 8317, 21739, 24029, 38299, ...	А181141
9	8	2, 7, 29, 31, 67, 149, 401, 2531, 19913, 30773, 53857, 170099, ...	А059803
9	7	3, 5, 7, 4703, 30113, ...	А273010
9	5	3, 11, 17, 173, 839, 971, 40867, 45821, ...	А128346
9	4	2 (других нет)
9	2	2, 3, 5, 13, 29, 37, 1021, 1399, 2137, 4493, 5521, ...	А173718
9	1	(никто)
9	−1	3, 59, 223, 547, 773, 1009, 1823, 3803, 49223, 193247, 703393, ...	А057175
9	−2	2 * , 3, 7, 127, 283, 883, 1523, 4001, ...	А125956
9	−4	2 * , 3, 5, 7, 11, 17, 19, 41, 53, 109, 167, 2207, 3623, 5059, 5471, 7949, 21211, 32993, 60251, ...	А211409
9	−5	3, 5, 13, 17, 43, 127, 229, 277, 6043, 11131, 11821, ...	А128339
9	−7	2 * , 3, 107, 197, 2843, 3571, 4451, ..., 31517, ...	А301369
9	−8	3, 7, 13, 19, 307, 619, 2089, 7297, 75571, 76103, 98897, ...	А187819
10	9	2, 3, 7, 11, 19, 29, 401, 709, 2531, 15787, 66949, 282493, ...	А062576
10	7	2, 31, 103, 617, 10253, 10691, ...	А273403
10	3	2, 3, 5, 37, 599, 38393, 51431, ...	А128026
10	1	2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, ...	А004023
10	−1	5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ...	А001562
10	−3	2 * , 3, 19, 31, 101, 139, 167, 1097, 43151, 60703, 90499, ...	А128069
10	−7	2 * , 3, 5, 11, 19, 1259, 1399, 2539, 2843, 5857, 10589, ...
10	−9	4 * , 7, 67, 73, 1091, 1483, 10937, ...	А217095
11	10	3, 5, 19, 311, 317, 1129, 4253, 7699, 18199, 35153, 206081, ...	А062577
11	9	5, 31, 271, 929, 2789, 4153, ...	А273601
11	8	2, 7, 11, 17, 37, 521, 877, 2423, ...	А273600
11	7	5, 19, 67, 107, 593, 757, 1801, 2243, 2383, 6043, 10181, 11383, 15629, ...	А273599
11	6	2, 3, 11, 163, 191, 269, 1381, 1493, ...	А273598
11	5	5, 41, 149, 229, 263, 739, 3457, 20269, 98221, ...	А128347
11	4	3, 5, 11, 17, 71, 89, 827, 22307, 45893, 63521, ...	А216181
11	3	3, 5, 19, 31, 367, 389, 431, 2179, 10667, 13103, 90397, ...	А128027
11	2	2, 5, 11, 13, 331, 599, 18839, 23747, 24371, 29339, 32141, 67421, ...	А210506
11	1	17, 19, 73, 139, 907, 1907, 2029, 4801, 5153, 10867, 20161, 293831, ...	А005808
11	−1	5, 7, 179, 229, 439, 557, 6113, 223999, 327001, ...	А057177
11	−2	3, 5, 17, 67, 83, 101, 1373, 6101, 12119, 61781, ...	А125957
11	−3	3, 103, 271, 523, 23087, 69833, ...	А128070
11	−4	2 * , 7, 53, 67, 71, 443, 26497, ...	А224501
11	−5	7, 11, 181, 421, 2297, 2797, 4129, 4139, 7151, 29033, ...	А128340
11	−6	2 * , 5, 7, 107, 383, 17359, 21929, 26393, ...
11	−7	7, 1163, 4007, 10159, ...
11	−8	2 * , 3, 13, 31, 59, 131, 223, 227, 1523, ...
11	−9	2 * , 3, 17, 41, 43, 59, 83, ...
11	−10	53, 421, 647, 1601, 35527, ...	А185239
12	11	2, 3, 7, 89, 101, 293, 4463, 70067, ...	А062578
12	7	2, 3, 7, 13, 47, 89, 139, 523, 1051, ...	А273814
12	5	2, 3, 31, 41, 53, 101, 421, 1259, 4721, 45259, ...	А128348
12	1	2, 3, 5, 19, 97, 109, 317, 353, 701, 9739, 14951, 37573, 46889, 769543, ...	А004064
12	−1	2 * , 5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, ...	А057178
12	−5	2 * , 3, 5, 13, 347, 977, 1091, 4861, 4967, 34679, ...	А128341
12	−7	2 * , 3, 7, 67, 79, 167, 953, 1493, 3389, 4871, ...
12	−11	47, 401, 509, 8609, ...	А213216

^* Примечание: если b < 0 и n четное, то числа n не включаются в соответствующую последовательность OEIS.

Когда a = b + 1 , это ( b + 1) ^н − б ^н , разность двух последовательных совершенных n- х степеней, и если a ^н − б ^н является простым, то a должно быть b + 1 , поскольку оно делится на a − b .

Наименьшее n такое, что ( b + 1) ^н − б ^н является простым

2, 2, 2, 3, 2, 2, 7, 2, 2, 3, 2, 17, 3, 2, 2, 5, 3, 2, 5, 2, 2, 229, 2, 3, 3, 2, 3, 3, 2, 2, 5, 3, 2, 3, 2, 2, 3, 3, 2, 7, 2, 3, 37, 2, 3, 5, 58543, 2, 3, 2, 2, 3, 2, 2, 3, 2, 5, 3, 4663, 54517, 17, 3, 2, 5, 2, 3, 3, 2, 2, 47, 61, 19, ... (последовательность A058013 в ОЭИС )

Наименьшее b такое, что ( b + 1) ^{простое( п )} − б ^{простое( п )} является простым

1, 1, 1, 1, 5, 1, 1, 1, 5, 2, 1, 39, 6, 4, 12, 2, 2, 1, 6, 17, 46, 7, 5, 1, 25, 2, 41, 1, 12, 7, 1, 7, 327, 7, 8, 44, 26, 12, 75, 14, 51, 110, 4, 14, 49, 286, 15, 4, 39, 22, 109, 367, 22, 67, 27, 95, 80, 149, 2, 142, 3, 11, ... (последовательность A222119 в OEIS )

См. также

• Воссоединить
• Число Ферма
• Сила двух
• Константа Эрдеша – Борвейна
• Гипотезы Мерсенна
• Твистер Мерсенна
• Двойное число Мерсенна
• Prime95 / MPrime
• Отличный интернет-поиск простых чисел Мерсенна (GIMPS)
• Самое большое известное простое число
• Виферих простое
• Вагстафф Прайм
• Каллен Прайм
• Вудалл Прайм
• Прот Прайм
• Солинас Прайм
• Гипотеза Гиллиса
• Число Вильямса

Внешние ссылки

• «Число Мерсенна» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Домашняя страница ГИМПС
• Отчет GIMPS Milestones — на странице состояния представлены различные статистические данные о ходе поиска, которые обычно обновляются каждую неделю, включая прогресс в доказательстве порядка крупнейших известных простых чисел Мерсенна.
• GIMPS, известные коэффициенты чисел Мерсенна
• М _q = (8 х ) ² − (3 qy ) ² Свойство составных чисел Мерсенна с простым показателем (PDF)
• М _q = х ² + д · й ² дипломная работа по математике (PS)
• Грайм, Джеймс. «31 и простые числа Мерсенна» . Числофил . Брэйди Харан . Архивировано из оригинала 31 мая 2013 г. Проверено 6 апреля 2013 г.
• Основная библиография Мерсенна с гиперссылками на оригинальные публикации
• отчет о простых числах Мерсенна – подробное обнаружение (на немецком языке)
• ГИМПС вики
• Страница Мерсенна Уилла Эджингтона - содержит коэффициенты для небольших чисел Мерсенна.
• Известные коэффициенты чисел Мерсенна
• Десятичные цифры и английские названия простых чисел Мерсенна
• Главный любопытный: 2305843009213693951.
• http://www.leyland.vispa.com/numth/factorization/cunningham/2-.txt. Архивировано 5 ноября 2014 г. в Wayback Machine.
• http://www.leyland.vispa.com/numth/factorization/cunningham/2+.txt. Архивировано 2 мая 2013 г. в Wayback Machine.
• Последовательность OEIS A250197 (числа n такие, что левая примитивная часть Орифейля 2^n+1 является простой) – Факторизация чисел Мерсенна M _n ( n до 1280)
• Факторизация полностью факторизованных чисел Мерсенна
• Проект Каннингема, факторизация b ^н ± 1, б = 2, 3, 5, 6, 7, 10, 11, 12
• http://www.leyland.vispa.com/numth/factorization/cunningham/main.htm. Архивировано 4 марта 2016 г. в Wayback Machine.
• http://www.leyland.vispa.com/numth/factorization/anbn/main.htm. Архивировано 2 февраля 2016 г. в Wayback Machine.

Ссылки MathWorld

• Вайсштейн, Эрик В. «Число Мерсенна» . Математический мир .
• Вайсштейн, Эрик В. «Простое число Мерсенна» . Математический мир .