В математике простым числом Мерсенна называется простое число , которое на единицу меньше степени двойки . То есть это простое число вида M n = 2 n − 1 для некоторого целого числа n . Они названы в честь Марина Мерсенна , французского монаха-минима , изучавшего их в начале 17 века. Если n — составное число , то и 2 n − 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 n − 1 без требования простоты можно назвать числами Мерсенна . Однако иногда числа Мерсенна определяются с дополнительным требованием, чтобы n было простым. Наименьшее составное число Мерсенна с простым показателем n равно 2 11 − 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 n ), для которого является простым.
Также неизвестно, являются ли бесконечно многие числа Мерсенна с простыми показателями составными, хотя это следует из широко распространенных гипотез о простых числах, например, о бесконечности простых чисел Софи Жермен, конгруэнтных 3 ( mod 4 ). Для этих простых чисел p , 2 p + 1 (который также является простым) будет делить M p , например, 23 | М 11 , 47 | М 23 , 167 | М 83 , 263 | М 131 , 359 | М 179 , 383 | М 191 , 479 | М 239 и 503 | М 251 (последовательность А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 2 = 3 , M 3 = 7 , M 5 = 31 и M 7 = 127 , а поскольку первое простое число Мерсенна начинается с M 2 , все простые числа Мерсенна конгруэнтны 3 (по модулю 4). Кроме M 0 = 0 и M 1 = 1 , все остальные числа Мерсенна также конгруэнтны 3 (по модулю 4). Следовательно, в простой факторизации числа Мерсенна ( ≥ M 2 ) должен быть хотя бы один простой множитель, конгруэнтный 3 (mod 4).
Основная теорема о числах Мерсенна гласит, что если M p простое число, то показатель степени p также должен быть простым. Это следует из тождества
Хотя приведенные выше примеры могут предполагать, что M p является простым для всех простых чисел p , это не так, и наименьшим контрпримером является число Мерсенна.
Имеющиеся данные свидетельствуют о том, что случайно выбранное число Мерсенна с гораздо большей вероятностью окажется простым, чем произвольно выбранное нечетное целое число аналогичного размера. [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 году, были следующими:
Его список повторял известные простые числа того времени с показателями до 19. Его следующая запись, 31, была правильной, но затем список стал в значительной степени неверным, поскольку Мерсенн по ошибке включил M 67 и M 257 (которые являются составными) и опустил M 61 . , M 89 и M 107 (простые). Мерсенн мало рассказал о том, как он составил свой список. [5]
Эдуард Лукас доказал в 1876 году, что M 127 действительно является простым, как утверждал Мерсенн. Это было самое большое известное простое число за 75 лет до 1951 года, когда Ферье нашел большее простое число с помощью настольной вычислительной машины. [6] : стр. 22 M 61 было определено как простое в 1883 году Иваном Михеевичем Первушиным , хотя Мерсенн утверждал, что оно составное, и по этой причине его иногда называют числом Первушина. Это было второе по величине известное простое число, и оно оставалось таковым до 1911 года. Лукас обнаружил еще одну ошибку в списке Мерсенна в 1876 году, продемонстрировав, что M 67 является составным, не найдя множителя. Никакого множителя не было найдено до знаменитого выступления Фрэнка Нельсона Коула в 1903 году. [7] Не говоря ни слова, он подошел к доске и возвел 2 в 67-ю степень, затем вычел единицу, в результате чего получилось число 147 573 952 589 676 412 927 . На другой стороне доски он умножил 193 707 721 × 761 838 257 287 и получил то же число, а затем молча вернулся на свое место (под аплодисменты). [8] Позже он сказал, что на поиск результата у него ушло «три года воскресений». [9] Правильный список всех простых чисел Мерсенна в этом диапазоне чисел был завершен и тщательно проверен только примерно через три столетия после того, как Мерсенн опубликовал свой список.
Доступны быстрые алгоритмы поиска простых чисел Мерсенна, и по состоянию на июнь 2023 года [обновлять]шесть крупнейших известных простых чисел являются простыми числами Мерсенна.
Первые четыре простых числа Мерсенна М 2 = 3 , М 3 = 7 , М 5 = 31 и М 7 = 127 были известны еще в древности. Пятый, М 13 = 8191 , был открыт анонимно до 1461 г.; следующие два ( M 17 и M 19 ) были найдены Пьетро Катальди в 1588 году. Спустя почти два столетия Леонард Эйлер в 1772 году подтвердил, что M 31 является простым . Следующим (в историческом, а не числовом порядке) было M 127 , найден Эдуардом Лукасом в 1876 году, затем М 61 Иваном Михеевичем Первушиным в 1883 году. Еще два ( М 89 и М 107 ) были найдены в начале 20 века Р.Э. Пауэрсом в 1911 и 1914 годах соответственно.
Наиболее эффективным методом, известным в настоящее время для проверки простоты чисел Мерсенна, является тест простоты Лукаса-Лемера . В частности, можно показать, что для простого числа p > 2 M p = 2 p − 1 является простым тогда и только тогда, когда M p делит S p − 2 , где S 0 = 4 и S k = ( S k − 1 ) 2 − 2 для k > 0 .
В эпоху ручных вычислений все показатели степени до 257 включительно были проверены с помощью теста Лукаса-Лемера и оказались составными. Заметный вклад внес отставной профессор физики Йельского университета Гораций Скаддер Улер, который выполнил расчеты для показателей 157, 167, 193, 199, 227 и 229. [10] К сожалению для этих исследователей, интервал, который они тестировали, содержит самый большой из известных относительный разрыв между простыми числами Мерсенна: следующий показатель степени простых чисел Мерсенна, 521, окажется более чем в четыре раза больше, чем предыдущий рекорд 127.
Поиск простых чисел Мерсенна произвел революцию с появлением электронного цифрового компьютера. Алан Тьюринг искал их на Манчестерском корабле Mark 1 в 1949 году, [11] но первая успешная идентификация простого числа Мерсенна, M 521 , была достигнута с помощью этого средства в 22:00 30 января 1952 года с использованием Национального бюро США. Западный автоматический компьютер по стандартам (SWAC) в Институте численного анализа Калифорнийского университета в Лос-Анджелесе под руководством Д. Х. Лемера с программой компьютерного поиска, написанной и управляемой профессором Р. М. Робинсоном . Это было первое простое число Мерсенна, идентифицированное за тридцать восемь лет; следующий, M 607 , был найден компьютером чуть менее чем через два часа. Еще три — M 1279 , M 2203 и M 2281 — были найдены той же программой в течение следующих нескольких месяцев. М 4423 было первым обнаруженным простым числом, содержащим более 1000 цифр, М 44 497 было первым с числом более 10 000, а М 6 972 593 было первым с числом более миллиона. В общем, количество цифр в десятичном представлении M n равно ⌊ n × log 10 2⌋ + 1 , где ⌊ x ⌋ обозначает функцию пола (или, что то же самое, ⌊log 10 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]
По состоянию на 2023 год [обновлять]51 известное простое число Мерсенна равно 2 p − 1 для следующих p :
Поскольку простые числа Мерсенна делятся только на 1 и на себя. Однако не все числа Мерсенна являются простыми числами Мерсенна. Числа Мерсенна являются очень хорошими тестовыми примерами для алгоритма сита специального числового поля , поэтому часто самым большим числом, факторизованным с помощью этого алгоритма, было число Мерсенна. По состоянию на июнь 2019 года [обновлять]рекордсменом является число 2 1,193 − 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 1277 является наименьшим составным числом Мерсенна без известных коэффициентов; у него нет простых множителей ниже 2 68 , [28] и очень маловероятно, что он будет иметь множители ниже 10 65 (~ 2 216 ). [29]
В таблице ниже показаны факторизации первых 20 составных чисел Мерсенна (последовательность A244453 в OEIS ).
Количество факторов для первых 500 чисел Мерсенна можно найти по адресу (последовательность A046800 в OEIS ).
В математической задаче «Ханойская башня » решение головоломки с башней из n дисков требует M n шагов, при условии, что ошибок не допущено. [30] Число рисовых зерен на всей шахматной доске в задаче о пшенице и шахматной доске равно M 64 . [31]
Астероид с номером малой планеты 8191 назван 8191 Мерсенн в честь Марина Мерсенна, потому что 8191 является простым числом Мерсенна ( 3 Юноны , 7 Ирис , 31 Евфросинии и 127 Иоганна были открыты и названы в 19 веке). [32]
В геометрии целочисленный прямоугольный треугольник , который является примитивным и имеет четную сторону, степень 2 ( ≥ 4 ), порождает уникальный прямоугольный треугольник, такой, что его внутренний радиус всегда является числом Мерсенна. Например, если четный участок равен 2 n + 1 , то, поскольку он примитивен, он ограничивает нечетный участок равным 4 n - 1 , гипотенузу - 4 n + 1 , а ее радиус - 2 n - 1 . [33]
Число Мерсенна – Ферма определяется как2 п р - 1/2 п р - 1 - 1 с p простым, r натуральным числом и может быть записано как MF( p , r ) . Когда r = 1 , это число Мерсенна. Когда p = 2 , это число Ферма . Единственные известные простые числа Мерсенна – Ферма с r > 1 :
Фактически, MF( p , r ) = Φ p r (2) , где Φ — круговой многочлен .
Простейшие обобщенные простые числа Мерсенна — это простые числа вида f (2 n ) , где f ( x ) — многочлен низкой степени с малыми целыми коэффициентами . [35] Пример: 2 64 − 2 32 + 1 , в данном случае n = 32 и f ( x ) = x 2 − x + 1 ; другой пример: 2 192 - 2 64 - 1 , в данном случае n = 64 и f ( x ) = x 3 - x - 1 .
Также естественно попытаться обобщить простые числа вида 2 n − 1 до простых чисел вида b n − 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 ) n − 1 является гауссовским простым числом , которое будет тогда будет называться гауссовым простым числом Мерсенна . [36]
(1 + i ) n − 1 является гауссовым простым числом для следующих n :
Подобно последовательности показателей обычных простых чисел Мерсенна, эта последовательность содержит только (рациональные) простые числа.
Что касается всех гауссовских простых чисел, нормы (то есть квадраты абсолютных значений) этих чисел являются рациональными простыми числами:
Можно встретить случаи, когда такое простое число Мерсенна также является простым числом Эйзенштейна , имея вид b = 1 + ω и b = 1 − ω . В этих случаях такие числа называются простыми числами Эйзенштейна-Мерсенна .
(1 + ω ) n − 1 является простым числом Эйзенштейна для следующих n :
Нормы (то есть квадраты абсолютных значений) этих простых чисел Эйзенштейна являются рациональными простыми числами:
Другой способ справиться с тем фактом, что b n − 1 всегда делится на b − 1 , — это просто исключить этот множитель и спросить, какие значения n составляют
быть главным. (Целое число b может быть как положительным, так и отрицательным.) Если, например, мы возьмем b = 10 , мы получим n значений:
Эти простые числа называются простыми числами повторения. Другой пример: когда мы берем b = −12 , мы получаем n значений:
Это гипотеза о том, что для каждого целого числа b , не являющегося полной степенью , существует бесконечно много значений n таких, чтоб н - 1/б - 1является простым. (Когда b — идеальная степень, можно показать, что существует не более одного значения n такого, чтоб н - 1/б - 1это просто)
Наименьшее n такое, чтоб н - 1/б - 1является простым (начиная с b = 2 , 0 , если такого n не существует)
Для отрицательных оснований b это (начиная с b = −2 , 0 , если такого n не существует)
Наименьшее основание b такое, чтоб простое( п ) - 1/б - 1является простым
Для отрицательных оснований b они равны
Другое обобщенное число Мерсенна:
где a , b любые взаимно простые целые числа, a > 1 и − a < b < a . (Поскольку a n − b n всегда делится на a − b , деление необходимо, чтобы была возможность найти простые числа.) [a] Мы можем спросить, какое n делает это число простым. Можно показать, что такое n само должно быть простым числом или равняться 4, а n может быть равно 4 тогда и только тогда, когда a + b = 1 и a 2 + b 2 — простое число. [b] Это гипотеза, что для любой пары ( a , b ) , такой что a и b не являются одновременно совершенными r- ми степенями для любого r и −4 ab не является идеальной четвертой степенью , существует бесконечно много значений n , таких чтоа н - б н/а - бявляется простым. [c] Однако это не было доказано ни для одного значения ( a , b ) .
* Примечание: если b < 0 и n четное, то числа n не включаются в соответствующую последовательность OEIS.
Когда a = b + 1 , это ( b + 1) n − b n , разность двух последовательных совершенных n- х степеней, и если a n − b n простое, то a должно быть b + 1 , потому что это делится на a - b .
Наименьшим n таким, что ( b + 1) n − b n является простым, являются
Наименьшим b таким, что ( b + 1) prime( n ) − b prime( n ) является простым, являются