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

Простое число вида (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 .

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

По состоянию на 2024 год ^{[ссылка]}известно 52 простых числа Мерсенна. Наибольшее известное простое число , 2 ^{136 279 841} − 1 , является простым числом Мерсенна. ^{[1] [2]} С 1997 года все вновь найденные простые числа Мерсенна были обнаружены в рамках проекта Great Internet Mersenne Prime Search , проекта распределенных вычислений . В декабре 2020 года был пройден важный этап в проекте после того, как все показатели ниже 100 миллионов были проверены хотя бы один раз. ^[3]

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

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

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

(еще нерешенные проблемы по математике)

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

Гипотеза Ленстры –Померанса–Вагстаффа утверждает, что существует бесконечно много простых чисел Мерсенна, и предсказывает порядок их роста и частоту: для каждого числа 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 | M ₁₁ , 47 | M ₂₃ , 167 | M ₈₃ , 263 | M ₁₃₁ , 359 | M ₁₇₉ , 383 | M ₁₉₁ , 479 | M ₂₃₉ и 503 | M ₂₅₁ (последовательность A002515 в OEIS ). Так как для этих простых чисел p , 2 p + 1 сравнимо с 7 mod 8, то 2 является квадратичным вычетом mod 2 p + 1 , и мультипликативный порядок 2 mod 2 p + 1 должен делить . Так как p является простым числом, то он должен быть p или 1. Однако он не может быть 1, так как и 1 не имеет простых множителей , поэтому он должен быть p . Следовательно, 2 p + 1 делится и не может быть простым числом. Первые четыре простых числа Мерсенна — это M ₂ = 3 , M ₃ = 7 , M ₅ = 31 и M ₇ = 127 , и поскольку первое простое число Мерсенна начинается с M ₂ , все простые числа Мерсенна сравнимы с 3 (mod 4). За исключением M ₀ = 0 и M ₁ = 1 , все другие числа Мерсенна также сравнимы с 3 (mod 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 также должен быть простым. Это следует из тождества Это исключает простоту для чисел Мерсенна с составным показателем, таких как M ₄ = 2 ⁴ − 1 = 15 = 3 × 5 = (2 ² − 1) × (1 + 2 ² ) . $${\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 _p является простым числом для всех простых чисел p , это не так, и наименьшим контрпримером является число Мерсенна

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

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

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

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

Идеальные числа

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

История

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

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

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

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

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

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

Первые четыре простых числа Мерсенна M ₂ = 3 , M ₃ = 7 , M ₅ = 31 и M ₇ = 127 были известны в древности. Пятое, M ₁₃ = 8191 , было открыто анонимно до 1461 года; следующие два ( M ₁₇ и M ₁₉ ) были найдены Пьетро Катальди в 1588 году. Спустя почти два столетия M ₃₁ был подтвержден как простое число Леонардом Эйлером в 1772 году. Следующим (в историческом, а не числовом порядке) было M ₁₂₇ , найденное Эдуардом Люка в 1876 году, затем M ₆₁ Иваном Михеевичем Первушиным в 1883 году. Еще два ( M ₈₉ и M ₁₀₇ ) были найдены в начале 20-го века RE Powers в 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. ^[11] К сожалению для этих исследователей, интервал, который они проверяли, содержит самый большой известный относительный разрыв между простыми числами Мерсенна: следующий показатель простого числа Мерсенна, 521, оказался бы более чем в четыре раза больше предыдущего рекорда 127.

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

Поиск простых чисел Мерсенна был революционизирован с появлением электронного цифрового компьютера. Алан Тьюринг искал их на Manchester Mark 1 в 1949 году, ^[12] но первая успешная идентификация простого числа Мерсенна, M ₅₂₁ , таким способом была достигнута в 22:00 30 января 1952 года с использованием Western Automatic Computer (SWAC) Национального бюро стандартов США в Институте численного анализа Калифорнийского университета в Лос-Анджелесе (UCLA) под руководством DH Lehmer , с помощью программы компьютерного поиска, написанной и запущенной профессором RM Robinson . Это было первое простое число Мерсенна, которое было идентифицировано за тридцать восемь лет; следующее, M ₆₀₇ , было найдено компьютером чуть менее чем через два часа. Еще три — M ₁₂₇₉ , M ₂₂₀₃ и M ₂₂₈₁  — были найдены той же программой в течение следующих нескольких месяцев. M _4,423 был первым простым числом, имеющим более 1000 цифр, M _44,497 был первым с более чем 10 000 цифр, а M _{6 972 593} был первым с более чем миллионом. В общем случае количество цифр в десятичном представлении M _n равно ⌊ n × log ₁₀ 2⌋ + 1 , где ⌊ x ⌋ обозначает функцию пола (или, что эквивалентно, ⌊log ₁₀ M _n ⌋ + 1 ).

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

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

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

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

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

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

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

12 октября 2024 года пользователь по имени Люк Дюрант из Сан-Хосе, Калифорния, нашел наибольшее известное на данный момент простое число Мерсенна, 2 ^{136 279 841} − 1 , имеющее 41 024 320 цифр. Это первое простое число Мерсенна с показателем, превосходящим 8 цифр. Об этом было объявлено 21 октября 2024 года. ^[24]

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

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

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

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

По состоянию на 2024 год ^{[обновлять]}52 известных простых числа Мерсенна равны 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, 2170, 1, 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, 136279841. (последовательность A000043 в OEIS )

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

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

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

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

Числа Мерсенна в природе и не только

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

Астероид с малой планетой номер 8191 назван 8191 Mersenne в честь Марина Мерсенна, поскольку 8191 является простым числом Мерсенна. ^[34]

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

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

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

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

Обобщения

Простейшими обобщенными простыми числами Мерсенна являются простые числа вида f (2 ⁿ ) , где f ( x ) — многочлен низкой степени с малыми целыми коэффициентами . ^[37] Примером является 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 ). Однако (см. также теоремы выше), 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 является гауссовым простым числом , которое затем будет называться гауссовым простым числом Мерсенна . ^[38]

(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, ... (последовательность 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 делают

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

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

2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, ... (последовательность A004023 в OEIS ),
соответствующие простым числам 11, 111111111111111111111, 1111111111111111111111111, ... (последовательность 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 в OEIS )

Для отрицательных оснований 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 ^{простое число( n )} − 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, 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 в OEIS )

Наименьшее 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 )( a ² + b ² ) . Таким образом, в этом случае пара ( a , b ) должна быть ( x + 1, − x ) и x ² + ( x + 1) ² должно быть простым числом. То есть, x должно быть в OEIS : A027861 .
3. Когда a и b являются совершенными степенями r для некоторого r > 1 или когда −4 ab является совершенной четвертой степенью, можно показать, что существует не более двух значений n с этим свойством: в этих случаях ⁠а ^н − б ^н/а − б⁠ можно разложить на множители алгебраически. ^{[ необходима ссылка ]}

Ссылки

1. "GIMPS обнаруживает самое большое известное простое число: 2136,279,841 − 1". Mersenne Research, Inc. 21 октября 2024 г. Получено 21 октября 2024 г.
2. "Проект GIMPS обнаружил самое большое известное простое число: 282,589,933-1". Mersenne Research, Inc. 21 декабря 2018 г. Получено 21 декабря 2018 г.
3. "GIMPS Milestones Report". Mersenne.org . Mersenne Research, Inc . Получено 5 декабря 2020 г. .
4. Колдуэлл, Крис. «Эвристика: вывод гипотезы Вагстаффа-Мерсенна».
5. Крис К. Колдуэлл, Простые числа Мерсенна: история, теоремы и списки
6. «Первые страницы», гипотеза Мерсенна.
7. Харди, Г. Х .; Райт, Э. М. (1959). Введение в теорию чисел (4-е изд.). Oxford University Press.
8. Cole, FN (1 декабря 1903 г.). «О факторизации больших чисел». Бюллетень Американского математического общества . 10 (3): 134–138. doi : 10.1090/S0002-9904-1903-01079-9 .
9. Белл, Э. Т. и Математическая ассоциация Америки (1951). Математика, королева и служанка науки . McGraw-Hill, Нью-Йорк.стр. 228.
10. "h2g2: Числа Мерсенна". BBC News . Архивировано из оригинала 5 декабря 2014 года.
11. Гораций С. Улер (1952). «Краткая история исследований чисел Мерсенна и последних огромных простых чисел». Scripta Mathematica . 18 : 122–131.
12. Брайан Нэппер, Математический факультет и Марк 1.
13. Maugh II, Thomas H. (2008-09-27). «Математики Калифорнийского университета в Лос-Анджелесе открыли простое число из 13 миллионов цифр». Los Angeles Times . Получено 21 мая 2011 г.
14. Тиа Гхоуз. «Обнаружено самое большое простое число». Scientific American . Получено 2013-02-07 .
15. Купер, Кертис (7 января 2016 г.). «Открытие простого числа Мерсенна – 274207281 − 1 является простым числом!». Mersenne Research, Inc. Получено 22 января 2016 г.
16. Брук, Роберт (19 января 2016 г.). «Простое число с 22 миллионами цифр — самое большое из когда-либо найденных». New Scientist . Получено 19 января 2016 г.
17. Чанг, Кеннет (21 января 2016 г.). «Новое самое большое простое число = 2 в 74-й степени... Э-э, оно большое». The New York Times . Получено 22 января 2016 г.
18. "Вехи". Архивировано из оригинала 2016-09-03.
19. "Открытие простого числа Мерсенна - 2^77232917-1 - простое число!". www.mersenne.org . Получено 03.01.2018 .
20. "Наибольшее известное простое число найдено на церковном компьютере". christianchronicle.org . 12 января 2018 г.
21. «Найдено: особое, ошеломляюще большое простое число». 5 января 2018 г.
22. "GIMPS обнаруживает самое большое известное простое число: 2^82,589,933-1" . Получено 01.01.2019 .
23. "GIMPS - The Math - PrimeNet". www.mersenne.org . Получено 29 июня 2021 г. .
24. «Открытие простого числа Мерсенна — 2136279841-1 — простое число!». www.mersenne.org . Получено 21 октября 2024 г.
25. Страница Мерсенна Уилла Эджингтона, архив 2014-10-14 на Wayback Machine
26. Колдуэлл, Крис К. «Доказательство результата Эйлера и Лагранжа о дивизорах Мерсенна». Prime Pages .
27. Кляйнъюнг, Торстен; Бос, Йоппе В.; Ленстра, Арьен К. (2014). «Фабрика факторизации Мерсенна». Достижения в криптологии – ASIACRYPT 2014 . Конспекты лекций по информатике. Том. 8874. стр. 358–377. дои : 10.1007/978-3-662-45611-8_19. ISBN 978-3-662-45607-1.
28. Анри Лифшиц и Рено Лифшиц. "PRP Top Records" . Получено 05.09.2022 .
29. "M12720787 Подробности экспоненты числа Мерсенна". www.mersenne.ca . Получено 5 сентября 2022 г. .
30. "Статус экспоненты для M1277" . Получено 2021-07-21 .
31. "Детали экспоненты числа Мерсенна M1277". www.mersenne.ca . Получено 24 июня 2022 г. .
32. Петкович, Миодраг (2009). Знаменитые головоломки великих математиков . Книжный магазин AMS. стр. 197. ISBN 978-0-8218-4814-2.
33. Weisstein, Eric W. "Проблема пшеницы и шахматной доски". Mathworld. Wolfram . Получено 11.02.2023 .
34. Алан Чемберлин. "JPL Small-Body Database Browser". Ssd.jpl.nasa.gov . Получено 21.05.2011 .
35. "OEIS A016131". Онлайновая энциклопедия целочисленных последовательностей.
36. "Исследование простых чисел Мерсенна и Ферма". Архивировано из оригинала 29-05-2012.
37. Солинас, Джером А. (1 января 2011 г.). «Обобщенное простое число Мерсенна». В Tilborg, Henk CA van; Jajodia, Sushil (ред.). Энциклопедия криптографии и безопасности . Springer US. стр. 509–510. doi :10.1007/978-1-4419-5906-5_32. ISBN 978-1-4419-5905-8.
38. Крис Колдуэлл: The Prime Glossary: ​​Гауссовский Мерсенн (часть Prime Pages )
39. (x, 1) и (x, −1) для x = от 2 до 50
40. (x, 1) для x = от 2 до 160
41. (x, −1) для x = от 2 до 160
42. (x + 1, x) для x = от 1 до 160
43. (x + 1, −x) для x = от 1 до 40
44. (x + 2, x) для нечетных x = от 1 до 107
45. (x, −1) для x = от 2 до 200
46. Записи PRP, поиск ⁠ ( a n − b n ) / c {\displaystyle (a^{n}-b^{n})/c} ⁠, то есть (a, b)
47. Записи PRP, поиск ⁠ ( a n + b n ) / c {\displaystyle (a^{n}+b^{n})/c} ⁠, то есть (a, −b)

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

• «Число Мерсенна», Энциклопедия математики , EMS Press , 2001 [1994]
• Домашняя страница GIMP
• Отчет о вехах GIMPS – страница статуса содержит различные статистические данные о ходе поиска, которые обычно обновляются каждую неделю, включая прогресс в доказательстве порядка крупнейших известных простых чисел Мерсенна.
• GIMPS, известные множители чисел Мерсенна
• M _q = (8 x ) ² − (3 qy ) ² Свойство чисел Мерсенна с простым показателем степени, которые являются составными (PDF)
• M _q = x ² + d · y ² математическая работа (PS)
• Грайм, Джеймс. "31 и простые числа Мерсенна". Numberphile . Брэди Харан . Архивировано из оригинала 2013-05-31 . Получено 2013-04-06 .
• Библиография Мерсенна с гиперссылками на оригинальные публикации
• отчет о простых числах Мерсенна – подробное обнаружение (на немецком языке)
• GIMPS вики
• Страница Мерсенна Уилла Эджингтона – содержит множители для малых чисел Мерсенна
• Известные множители чисел Мерсенна
• Десятичные цифры и английские названия простых чисел Мерсенна
• Главные любопытства: 2305843009213693951.
• http://www.leyland.vispa.com/numth/factorization/cunningham/2-.txt Архивировано 2014-11-05 на Wayback Machine
• http://www.leyland.vispa.com/numth/factorization/cunningham/2+.txt Архивировано 2013-05-02 на 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 Архивировано 04.03.2016 на Wayback Machine
• http://www.leyland.vispa.com/numth/factorization/anbn/main.htm Архивировано 2016-02-02 на Wayback Machine

Ссылки MathWorld

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