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

Простое число формы (2^n)-1

В математике простым числом Мерсенна называется простое число , которое на единицу меньше степени двойки . То есть это простое число вида M _n = 2 ⁿ − 1 для некоторого целого числа n . Они названы в честь Марина Мерсенна , французского монаха-минима , изучавшего их в начале 17 века. Если n — составное число , то и 2 ⁿ − 1 тоже . Следовательно, эквивалентное определение простых чисел Мерсенна состоит в том, что они являются простыми числами вида M _p = 2 ^p − 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 , является простым числом Мерсенна. ^[1] С 1997 года все вновь найденные простые числа Мерсенна обнаруживаются в рамках проекта распределенных вычислений Great Internet Mersenne Prime Search . В декабре 2020 года была пройдена важная веха в проекте после того, как все показатели ниже 100 миллионов были проверены хотя бы один раз. ^[2]

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

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

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

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

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

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

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

Основная теорема о числах Мерсенна гласит, что если M _p простое число, то показатель степени p также должен быть простым. Это следует из тождества

$${\displaystyle {\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 .

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

Поиск простых чисел Мерсенна произвел революцию с появлением электронного цифрового компьютера. Алан Тьюринг искал их на Манчестерском корабле Mark 1 в 1949 году ^[11] , но первая успешная идентификация простого числа Мерсенна, 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]

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. ^[13]

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

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

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

21 декабря 2018 года было объявлено, что Великий интернет-поиск простых чисел Мерсенна (GIMPS) обнаружил самое большое известное простое число, 2 ^{82 589 933} - 1 , содержащее 24 862 048 цифр. Компьютер, добровольно предоставленный Патриком Ларошем из Окалы, Флорида, сделал находку 7 декабря 2018 года. ^[21]

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

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

1. Если a и p — натуральные числа такие, что a ^p − 1 простое, то a = 2 или p = 1 .
   • Доказательство : а ≡ 1 ( mod a - 1) . Тогда a ^p ≡ 1 (mod a − 1) , поэтому a ^p − 1 ≡ 0 (mod a − 1) . Таким образом, а − 1 | а ^п - 1 . Однако a ^p − 1 является простым, поэтому a − 1 = a ^p − 1 или a − 1 = ±1 . В первом случае a = a ^p , следовательно, a = 0, 1 (что является противоречием, поскольку ни −1, ни 0 не являются простыми числами) или p = 1. Во втором случае a = 2 или a = 0 . Однако если a = 0 , 0 ^p − 1 = 0 − 1 = −1 , что не является простым числом. Следовательно, а = 2 .
2. Если 2 ^p − 1 простое число, то p простое число.
   • Доказательство : предположим, что p составное, поэтому можно записать p = ab с a и b > 1 . Тогда 2 ^p - 1 = 2 ^ab - 1 = (2 ^a ) ^b - 1 = (2 ^a - 1) ( (2 ^a ) ^{b -1} + (2 ^a ) ^{b -2} + ... + 2 ^a + 1 ) , поэтому 2 ^p − 1 составное. Напротив, если 2 ^p − 1 простое число, то p простое число.
3. Если p — нечетное простое число, то каждое простое число q , делящее 2 ^p − 1, должно быть равно 1 плюс кратное 2 p . Это справедливо даже тогда, когда 2 ^p − 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 ^p − 1 , для всех натуральных чисел c q также является фактором 2 ^pc − 1 . Поскольку p — простое число и q не является фактором 2 ¹ − 1 , p также является наименьшим положительным целым числом x таким, что q является фактором 2 ^x − 1 . В результате для всех натуральных чисел x q является фактором 2 ^x − 1 тогда и только тогда, когда p является фактором x . Следовательно, поскольку q является фактором 2 ^{q −1} − 1 , p является фактором q − 1 , поэтому q ≡ 1 (mod p ) . Более того, поскольку q является коэффициентом 2 ^p − 1 , что нечетно, q нечетно. Следовательно, q ≡ 1 (mod 2 p ) .
   • Этот факт приводит к доказательству теоремы Евклида , которая утверждает бесконечность простых чисел, в отличие от доказательства, написанного Евклидом: для каждого нечётного простого числа p все простые числа, делящие 2 ^p − 1 , больше, чем p ; таким образом, всегда существуют простые числа большего размера, чем любое конкретное простое число.
   • Из этого факта следует, что для каждого простого числа _p > 2 существует хотя бы одно простое число вида 2kp +1 , меньшее или равное Mp , для некоторого целого числа k .
4. Если p — нечетное простое число, то каждое простое число q , делящее 2 ^p − 1 , конгруэнтно ±1 (по модулю 8) .
   • Доказательство : 2 ^{p +1} ≡ 2 (mod q ) , поэтому 2^1/2(p+1) является квадратным корнем из 2 по модулю q . По квадратичной взаимности каждый простой модуль, в котором число 2 имеет квадратный корень, конгруэнтен ±1 (mod 8) .
5. Простое число Мерсенна не может быть простым числом Вифериха .
   • Доказательство : мы покажем, что если p = 2 ^m − 1 является простым числом Мерсенна, то сравнение 2 ^{p −1} ≡ 1 (mod p ² ) не выполняется. По малой теореме Ферма m | п - 1 . Следовательно, можно написать p − 1 = mλ . Если данное сравнение выполнено, то p ² | 2 ^mλ − 1 , следовательно, 0 ≡2 ^мλ − 1/2 ^м − 1 знак равно 1 + 2 ^м + 2 ^{2 м} + ... + 2 ^{( λ - 1) м} ≡ - λ mod (2 ^м - 1) . Следовательно, 2 ^м − 1 | λ , и, следовательно, λ ≥ 2 ^м - 1 . Это приводит к тому, что p − 1 ≥ m (2 ^m − 1) , что невозможно, поскольку m ≥ 2 .
6. Если m и n — натуральные числа, то m и n взаимно просты тогда и только тогда, когда 2 ^m − 1 и 2 ⁿ − 1 взаимно просты. Следовательно, простое число делит не более одного числа Мерсенна в простой степени. ^[23] То есть набор пагубных чисел Мерсенна попарно взаимно прост.
7. Если p и 2 p + 1 оба простые (это означает, что p — простое число Софи Жермен ), и p конгруэнтно 3 (по модулю 4) , то 2 p + 1 делит 2 ^p − 1 . ^[24]
   • Пример : 11 и 23 оба простые, и 11 = 2 × 4 + 3 , поэтому 23 делит 2 ¹¹ − 1 .
   • Доказательство : Пусть q равно 2p + 1 . По малой теореме Ферма 2 ^{2 p} ≡ 1 (mod q ) , поэтому либо 2 ^p ≡ 1 (mod q ) , либо 2 ^p ≡ −1 (mod q ) . Предположим, что последнее верно, тогда 2 ^{p +1} = (2^{1/2( p + 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 ^m − 1 = nk не имеет решений, где m , n и k — ^целые числа с m > 1 и k > 1 .

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

По состоянию на 2023 год ^{[обновлять]}51 известное простое число Мерсенна равно 2 ^p − 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, 21701. , 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 2099601 1, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933. (последовательность A000043 в OEIS )

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

Поскольку простые числа Мерсенна делятся только на 1 и на себя. Однако не все числа Мерсенна являются простыми числами Мерсенна. Числа Мерсенна являются очень хорошими тестовыми примерами для алгоритма сита специального числового поля , поэтому часто самым большим числом, факторизованным с помощью этого алгоритма, было число Мерсенна. По состоянию на июнь 2019 года ^{[обновлять]}рекордсменом является число 2 ¹¹⁹³ − 1 , ^[25] которое было факторизовано с помощью варианта сита специального числового поля, которое позволяет факторизовать несколько чисел одновременно. См. записи целочисленной факторизации для получения ссылок на дополнительную информацию. Специальное сито числового поля может факторизовать числа с более чем одним большим фактором. Если число имеет только один очень большой фактор, то другие алгоритмы могут факторизовать большие числа, сначала находя малые факторы, а затем выполняя тест на простоту кофактора. По состоянию на сентябрь 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 равно 3829,2. 94-значное вероятное простое число. Его обнаружил участник GIMPS под ником «Funky Waddle». ^{[26] [27]} По состоянию на сентябрь 2022 года ^{[обновлять]}число Мерсенна M ₁₂₇₇ является наименьшим составным числом Мерсенна без известных коэффициентов; у него нет простых множителей ниже 2 ⁶⁸ , ^[28] и очень маловероятно, что он будет иметь множители ниже 10 ⁶⁵ (~ 2 ²¹⁶ ). ^[29]

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

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

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

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

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

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

Простые числа Мерсенна – Ферма

Число Мерсенна – Ферма определяется как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) . ^[34]

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

Обобщения

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

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

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

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

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

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

(1 + i ) ⁿ − 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, ... (последовательность А 057429 в ОЭИС )

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

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

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 составляют

${\displaystyle {\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 таких, чтоб ^н - 1/б - 1является простым. (Когда b — идеальная степень, можно показать, что существует не более одного значения n такого, чтоб ^н - 1/б - 1это просто)

Наименьшее n такое, чтоб ^н - 1/б - 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 такое, чтоб ^{простое( п )} - 1/б - 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 )

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

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

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

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

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

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

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

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) ^{prime( n )} − b ^{prime( n )} является простым, являются

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)
• Самое большое известное простое число
• Виферих простое
• Вагстафф Прайм
• Каллен Прайм
• Вудалл Прайм
• Прот Прайм
• Солинас Прайм
• Гипотеза Гиллиса
• Число Вильямса

Примечания

1. Это число совпадает с числом Люка U _n ( a + b , ab ) , поскольку a и b являются корнями квадратного уравнения x ² - ( a + b ) x + ab = 0 .
2. Посколькуа ⁴ - б ⁴/а - бзнак равно ( а + б )( а ² + б ² ) . Таким образом, в этом случае пара ( a , b ) должна быть ( x + 1, − x ) и x ² + ( x + 1) ² должно быть простым. То есть x должен быть в OEIS : A027861 .
3. Когда a и b являются совершенными r- ми степенями для некоторого r > 1 или когда −4 ab является идеальной четвертой степенью, можно показать, что существует не более двух значений n с этим свойством: в этих случаяха ^н - б ^н/а - бможно факторизовать алгебраически. ^{[ нужна цитата ]}

Рекомендации

1. «Проект GIMPS обнаружил самое большое известное простое число: 282 589 933-1» . Мерсенн Рисерч, Инк . 21 декабря 2018 года . Проверено 21 декабря 2018 г.
2. "Отчет об основных этапах работы GIMPS" . Мерсенн.орг . Мерсенн Рисерч, Инк . Проверено 5 декабря 2020 г.
3. Колдуэлл, Крис. «Эвристика: вывод гипотезы Вагстафа-Мерсенна».
4. Крис К. Колдуэлл, Простые числа Мерсенна: история, теоремы и списки
5. The Prime Pages, гипотеза Мерсенна.
6. Харди, GH ; Райт, Э.М. (1959). Введение в теорию чисел (4-е изд.). Издательство Оксфордского университета.
7. Коул, ФН (1 декабря 1903 г.). «О факторинге больших чисел». Бюллетень Американского математического общества . 10 (3): 134–138. дои : 10.1090/S0002-9904-1903-01079-9 .
8. Белл, ET и Математическая ассоциация Америки (1951). Математика, королева и слуга науки . МакГроу-Хилл, Нью-Йорк.п. 228.
9. "h2g2: Числа Мерсенна" . Новости BBC . Архивировано из оригинала 5 декабря 2014 года.
10. Гораций С. Улер (1952). «Краткая история исследований чисел Мерсенна и последних огромных простых чисел». Скрипта Математика . 18 : 122–131.
11. Брайан Нэппер, Отдел математики и Mark 1.
12. Мо II, Томас Х. (27 сентября 2008 г.). «Математики Калифорнийского университета в Лос-Анджелесе открыли простое число из 13 миллионов цифр». Лос-Анджелес Таймс . Проверено 21 мая 2011 г.
13. Тиа Гоуз. «Обнаружено самое большое простое число». Научный американец . Проверено 7 февраля 2013 г.
14. Купер, Кертис (7 января 2016 г.). «Открытие простого числа Мерсенна — 274207281 — 1 — простое число!». Мерсенн Рисерч, Инк . Проверено 22 января 2016 г.
15. Брук, Роберт (19 января 2016 г.). «Простое число из 22 миллионов цифр — самое большое из когда-либо найденных». Новый учёный . Проверено 19 января 2016 г.
16. Чанг, Кеннет (21 января 2016 г.). «Новое самое большое простое число = от 2 до 74 миллионов… Ох, оно большое». Нью-Йорк Таймс . Проверено 22 января 2016 г.
17. «Вехи». Архивировано из оригинала 3 сентября 2016 г.
18. "Мерсенн Прайм Дискавери - 2 ^ 77232917-1 - Прайм!" www.mersenne.org . Проверено 3 января 2018 г.
19. «Самое известное простое число, найденное на церковном компьютере» . christianchronicle.org . 12 января 2018 г.
20. «Найдено: особое, ошеломляюще большое простое число» . 5 января 2018 г.
21. «GIMPS обнаружил самое большое известное простое число: 2 ^ 82 589 933-1» . Проверено 1 января 2019 г.
22. "GIMPS - Математика - PrimeNet" . www.mersenne.org . Проверено 29 июня 2021 г.
23. Страница Мерсенна Уилла Эджингтона. Архивировано 14 октября 2014 г. в Wayback Machine.
24. Колдуэлл, Крис К. «Доказательство результата Эйлера и Лагранжа о делителях Мерсенна». Прайм страницы .
25. Кляйнъюнг, Торстен; Бос, Йоппе В.; Ленстра, Арьен К. (2014). «Фабрика факторизации Мерсенна». Достижения в криптологии – ASIACRYPT 2014 . Конспекты лекций по информатике. Том. 8874. стр. 358–377. дои : 10.1007/978-3-662-45611-8_19. ISBN 978-3-662-45607-1.
26. Анри Лифшиц и Рено Лифшиц. «Лучшие рекорды ПРП» . Проверено 05 сентября 2022 г.
27. "M12720787 Детали показателя степени числа Мерсенна" . www.mersenne.ca . Проверено 5 сентября 2022 г.
28. «Статус экспоненты для M1277» . Проверено 21 июля 2021 г.
29. "M1277 Подробности показателя числа Мерсенна" . www.mersenne.ca . Проверено 24 июня 2022 г.
30. Петкович, Миодраг (2009). Знаменитые загадки великих математиков . Книжный магазин АМС. п. 197. ИСБН 978-0-8218-4814-2.
31. Вайсштейн, Эрик В. «Проблема пшеницы и шахматной доски». Математический мир. Вольфрам . Проверено 11 февраля 2023 г.
32. Алан Чемберлин. «Обозреватель базы данных малых тел JPL». Ssd.jpl.nasa.gov . Проверено 21 мая 2011 г.
33. "OEIS A016131" . Интернет-энциклопедия целочисленных последовательностей.
34. «Исследование простых чисел Мерсенна и Ферма». Архивировано из оригинала 29 мая 2012 г.
35. Солинас, Джером А. (1 января 2011 г.). «Обобщенное простое число Мерсенна». В Тилборге, фургон Henk CA; Яджодиа, Сушил (ред.). Энциклопедия криптографии и безопасности . Спрингер США. стр. 509–510. дои : 10.1007/978-1-4419-5906-5_32. ISBN 978-1-4419-5905-8.
36. Крис Колдуэлл: Главный глоссарий: Гауссов Мерсенн (часть Prime Pages )
37. Залнежад, Али; Залнежад, Хоссейн; Шабани, Гасем; Залнежад, Мехди (март 2015 г.). «Отношения и алгоритм для получения наибольшего простого числа». arXiv : 1503.07688 [math.NT].
38. (x, 1) и (x, −1) для x от 2 до 50
39. (x, 1) для x = от 2 до 160
40. (x, −1) для x = 2 до 160
41. (x + 1, x) для x = от 1 до 160
42. (x + 1, −x) для x = от 1 до 40
43. (x + 2, x) для нечетных x = от 1 до 107
44. (x, −1) для x = от 2 до 200
45. записи PRP, найдите ( a n - b n ) / c {\displaystyle (a^{n}-b^{n})/c}, то есть (a, b)
46. записи PRP, найдите ( a n + b n ) / c {\displaystyle (a^{n}+b^{n})/c}, то есть (a, -b)

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

• «Число Мерсенна», Математическая энциклопедия , EMS Press , 2001 [1994]
• Домашняя страница ГИМПС
• Отчет GIMPS Milestones — страница состояния предоставляет различную статистику о ходе поиска, обычно обновляемую каждую неделю, включая прогресс в доказательстве порядка крупнейших известных простых чисел Мерсенна.
• GIMPS, известные коэффициенты чисел Мерсенна
• M _q = (8 x ) ² − (3 qy ) ² Свойство составных чисел Мерсенна с простым показателем (PDF)
• M _q = x ² + d · y ² дипломная работа по математике (ПС)
• Грайм, Джеймс. «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)
• Факторизация полностью факторизованных чисел Мерсенна
• Проект Каннингема, факторизация bn ± 1, b = 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

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