Простые числа Мерсенна: свойства и поиск

Введение

Простое число вида (2^n) – 1

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

Значения n, которые дают числа Мерсенна, равны 2, 3, 5, 7, 13, 17, 19, 31, а соответствующие числа Мерсенна равны 3, 7, 31, 127, 8191, 131071, 524287, 2147483647.
Числа вида 2^n – 1 без требования простоты могут называться числами Мерсенна. Иногда, однако, числа Мерсенна определяются с дополнительным требованием, чтобы n было простым числом. Наименьшее составное число Мерсенна с простым показателем n — это…

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

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

Мерсеннские простые числа Mp тесно связаны с совершенными числами. В IV веке до н.э. Евклид доказал, что если 2^(p) − 1 является простым числом, то 2^(p − 1)(2^(p) − 1) является совершенным числом. В XVIII веке Леонард Эйлер доказал, что, наоборот, все четные совершенные числа имеют именно такую форму. Это известно как теорема Евклида — Эйлера. Неизвестно, существуют ли нечетные совершенные числа.

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

Быстрые алгоритмы для поиска простых чисел Мерсена доступны, и по состоянию на 2023 год шесть самых больших известных простых чисел являются числами Мерсена. Первые четыре числа Мерсена, 2, 3, 5 и 7, были известны в древности. Пятое, 31, было обнаружено анонимно до 1461 года; следующие два (M17 и M19) были найдены Пьетро Катальди в 1588 году. После почти двух столетий, M31 был подтвержден как простое число Леонардом Эйлером в 1772 году. Следующим (в историческом, а не в числовом порядке) был M127, найденный Эдуардом Лукасом в 1876 году, затем M61 Иваном Михеевичем Первушиным в 1883 году. Еще два (M89 и M107) были найдены в начале 20-го века, Р. Э. Пауэрсом в 1911 и 1914 годах соответственно. Самым эффективным методом, известным в настоящее время для проверки простоты чисел Мерсена, является тест простоты Лукаса — Лемера. В частности, можно показать, что для простого p > 2, 2p − 1 является простым, если и только если Mp делит Sp-2, где Sn = 2n − 1 и для k > 0. В эпоху ручного вычисления все показатели до 257 были проверены с помощью теста Лукаса — Лемера и оказались составными. Заметный вклад внес отставной профессор физики Йельского университета Гораций Скаддер Улер, который выполнил вычисления для показателей 157, 167, 193, 199, 227 и 229. К сожалению для этих исследователей, интервал, который они тестировали, содержит самый большой известный относительный разрыв между простыми числами Мерсена: следующий показатель простого числа Мерсена, 521, оказался более чем в четыре раза больше предыдущего рекорда в 127. Поиск простых чисел Мерсена был революционизирован введением электронного цифрового компьютера. Алан Тьюринг искал их на Manchester Mark 1 в 1949 году, но первая успешная идентификация простого числа Мерсена, M521, была достигнута в 10:00 вечера 30 января 1952 года, используя Western Automatic Computer (SWAC) Национального бюро стандартов США в Институте численного анализа Калифорнийского университета в Лос-Анджелесе под руководством Д. Х. Лемера, с помощью компьютерной программы поиска, написанной и запущенной профессором Р. М. Робинсоном. Это было первое простое число Мерсена, идентифицированное за тридцать восемь лет; следующее, M607, было найдено компьютером чуть менее чем через два часа. Еще три — M1279, M2203 и M2281 — были найдены той же программой в течение следующих нескольких месяцев. M4423 было первым простым числом, обнаруженным с более чем 1000 цифр, M44497 — первым с более чем 10 000, а M6972593 — первым с более чем миллионом. В целом, число цифр в десятичном представлении Mn равно ⌊n × log102⌋ + 1, где ⌊x⌋ обозначает функцию взятия целой части (или эквивалентно ⌊log10Mn⌋ + 1). В сентябре 2008 года математики из UCLA, участвующие в Great Internet Mersenne Prime Search (GIMPS), выиграли часть приза в размере 100 000 долларов от Electronic Frontier Foundation за открытие почти 13-миллионного числа Мерсена. Приз, окончательно подтвержденный в октябре 2009 года, присуждается первому известному простому числу с не менее 10 миллионами цифр. Это число было найдено на Dell OptiPlex 745 23 августа 2008 года. Это было восьмое простое число Мерсена, открытое в UCLA. 12 апреля 2009 года в журнале сервера GIMPS сообщалось, что 47-е число Мерсена, возможно, было найдено. Находка была впервые замечена 4 июня 2009 года и подтверждена неделей позже. Это число равно 242643801 − 1. Хотя это хронологически 47-е открытое число Мерсена, оно меньше, чем самое большое из известных в то время, которое было 45-м открытым. 25 января 2013 года Кёртис Купер, математик из Университета Центрального Миссури, обнаружил 48-е число Мерсена, 257885161 − 1 (число с 17 425 170 цифрами), в результате поиска, выполненного сетью серверов GIMPS. 19 января 2016 года Купер опубликовал свое открытие 49-го простого числа Мерсена, 274207281 − 1 (число с 22 338 618 цифрами), в результате поиска, выполненного сетью серверов GIMPS. Это было четвертое число Мерсена, открытое Купером и его командой за последние десять лет. 2 сентября 2016 года Great Internet Mersenne Prime Search завершил проверку всех тестов ниже M37156667, таким образом официально подтвердив свою позицию как 45-го числа Мерсена. 3 января 2018 года было объявлено, что 51-летний инженер-электрик Джонатан Пейс, живущий в Германдауне, штат Теннесси, нашел 50-е число Мерсена, 277232917 − 1 (число с 23 249 425 цифрами), в результате поиска, выполненного сетью серверов GIMPS. Открытие было сделано компьютером в офисе церкви в том же городе. 21 декабря 2018 года было объявлено, что The Great Internet Mersenne Prime Search (GIMPS) обнаружил самое большое известное простое число, 282589933 − 1, имеющее 24 862 048 цифр. Компьютер, предоставленный Патриком Ларошем из Окалы, штат Флорида, сделал это открытие 7 декабря 2018 года. В конце 2020 года GIMPS начал использовать новую технику для исключения потенциальных простых чисел Мерсена, называемую тестом вероятного простого числа (PRP), основанную на разработке Роберта Гербица в 2017 году и простой способ проверки тестов, разработанный Кшиштофом Петржаком в 2018 году. Благодаря низкой вероятности ошибки и простоте доказательства это почти вдвое сократило время вычислений для исключения потенциальных простых чисел по сравнению с тестом Лукаса — Лемера (поскольку двум пользователям больше не нужно было выполнять один и тот же тест для подтверждения результата друг друга), хотя показатели, прошедшие тест PRP, все равно требуют одного подтверждения их простоты.

Fast algorithms for finding Mersenne primes are available, and as of 2023, the six largest known prime numbers are Mersenne primes. The first four Mersenne primes , , and were known in antiquity. The fifth, , was discovered anonymously before 1461; the next two (M17 and M19) were found by Pietro Cataldi in 1588. After nearly two centuries, M31 was verified to be prime by Leonhard Euler in 1772. The next (in historical, not numerical order) was M127, found by Édouard Lucas in 1876, then M61 by Ivan Mikheevich Pervushin in 1883. Two more (M89 and M107) were found early in the 20th century, by R. E. Powers in 1911 and 1914, respectively. The most efficient method presently known for testing the primality of Mersenne numbers is the Lucas–Lehmer primality test. Specifically, it can be shown that for prime p > 2, is prime if and only if Mp divides Sp − 2, where and for k > 0. During the era of manual calculation, all the exponents up to and including 257 were tested with the Lucas–Lehmer test and found to be composite. A notable contribution was made by retired Yale physics professor Horace Scudder Uhler, who did the calculations for exponents 157, 167, 193, 199, 227, and 229. Unfortunately for those investigators, the interval they were testing contains the largest known relative gap between Mersenne primes: the next Mersenne prime exponent, 521, would turn out to be more than four times as large as the previous record of 127. The search for Mersenne primes was revolutionized by the introduction of the electronic digital computer. Alan Turing searched for them on the Manchester Mark 1 in 1949, but the first successful identification of a Mersenne prime, M521, by this means was achieved at 10:00 pm on January 30, 1952, using the U. S. National Bureau of Standards Western Automatic Computer (SWAC) at the Institute for Numerical Analysis at the University of California, Los Angeles, under the direction of D. H. Lehmer, with a computer search program written and run by Prof. R. M. Robinson. It was the first Mersenne prime to be identified in thirty eight years; the next one, M607, was found by the computer a little less than two hours later. Three more — M1279, M2203, and M2281 — were found by the same program in the next several months. M4,423 was the first prime discovered with more than 1000 digits, M44,497 was the first with more than 10,000, and M6,972,593 was the first with more than a million. In general, the number of digits in the decimal representation of Mn equals ⌊n × log102⌋ + 1, where ⌊x⌋ denotes the floor function (or equivalently ⌊log10Mn⌋ + 1). In September 2008, mathematicians at UCLA participating in the Great Internet Mersenne Prime Search (GIMPS) won part of a $100,000 prize from the Electronic Frontier Foundation for their discovery of a very nearly 13 million digit Mersenne prime. The prize, finally confirmed in October 2009, is for the first known prime with at least 10 million digits. The prime was found on a Dell OptiPlex 745 on August 23, 2008. This was the eighth Mersenne prime discovered at UCLA. On April 12, 2009, a GIMPS server log reported that a 47th Mersenne prime had possibly been found. The find was first noticed on June 4, 2009, and verified a week later. The prime is 242,643,801 − 1. Although it is chronologically the 47th Mersenne prime to be discovered, it is smaller than the largest known at the time, which was the 45th to be discovered. On January 25, 2013, Curtis Cooper, a mathematician at the University of Central Missouri, discovered a 48th Mersenne prime, 257,885,161 − 1 (a number with 17,425,170 digits), as a result of a search executed by a GIMPS server network. On January 19, 2016, Cooper published his discovery of a 49th Mersenne prime, 274,207,281 − 1 (a number with 22,338,618 digits), as a result of a search executed by a GIMPS server network. This was the fourth Mersenne prime discovered by Cooper and his team in the past ten years. On September 2, 2016, the Great Internet Mersenne Prime Search finished verifying all tests below M37,156,667, thus officially confirming its position as the 45th Mersenne prime. On January 3, 2018, it was announced that Jonathan Pace, a 51 year old electrical engineer living in Germantown, Tennessee, had found a 50th Mersenne prime, 277,232,917 − 1 (a number with 23,249,425 digits), as a result of a search executed by a GIMPS server network. The discovery was made by a computer in the offices of a church in the same town. On December 21, 2018, it was announced that The Great Internet Mersenne Prime Search (GIMPS) discovered the largest known prime number, 282,589,933 − 1, having 24,862,048 digits. A computer volunteered by Patrick Laroche from Ocala, Florida made the find on December 7, 2018. In late 2020, GIMPS began using a new technique to rule out potential Mersenne primes called the Probable prime (PRP) test, based on development from Robert Gerbicz in 2017, and a simple way to verify tests developed by Krzysztof Pietrzak in 2018. Due to the low error rate and ease of proof, this nearly halved the computing time to rule out potential primes over the Lucas Lehmer test (as two users would no longer have to perform the same test to confirm the other's result), although exponents passing the PRP test still require one to confirm their primality.

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

Если $a$ и $p$ – натуральные числа, такие, что $a^p - 1$ является простым, то либо $a = 1$, либо $p = 1$. Доказательство: $a \equiv 1 \pmod{a-1}$. Тогда $a^p \equiv 1 \pmod{a-1}$, так что $a^p - 1 \equiv 0 \pmod{a-1}$. Таким образом, $a^p - 1$ делится на $a-1$. Поскольку $a^p - 1$ является простым, то либо $a-1 = 1$, либо $a-1 = a^p - 1$. В первом случае, $a = 2$, следовательно, $2^p - 1$ является простым (что является противоречием, так как ни $-1$, ни $0$ не являются простыми), либо $p = 1$. Во втором случае, $a^p = a$, следовательно, $p = 1$ или $a = 1$. Если $p = 1$, то $a^1 - 1 = a - 1$, что не является простым. Поэтому, если $2^p - 1$ является простым, то $p$ является простым. Доказательство: Предположим, что $p$ является составным, следовательно, может быть записано в виде $p = ab$ с $a$ и $b > 1$. Тогда $2^p - 1 = 2^{ab} - 1 = (2^a)^b - 1$, что делится на $2^a - 1$, так что $2^p - 1$ является составным. По контрапозиции, если $2^p - 1$ является простым, то $p$ является простым. Если $p$ – нечетное простое число, то каждое простое число $q$, которое делит $2^p - 1$, должно быть равно $1$ плюс кратное $2p$. Это верно даже когда $2^p - 1$ является простым числом. Например, $3$ является простым, и $7$ является составным примером, где $p = 3$ и $q = 7$. Доказательство: По малой теореме Ферма, $q$ является делителем $2^{q-1} - 1$. Поскольку $q$ является делителем $2^p - 1$, для всех положительных целых чисел $c$, $q$ также является делителем $2^{pc} - 1$. Поскольку $p$ – простое число, а $q$ не является делителем $2^1 - 1 = 1$, $p$ также является наименьшим положительным целым числом $x$, таким, что $q$ является делителем $2^x - 1$. В результате, для всех положительных целых чисел $x$, $q$ является делителем $2^x - 1$ тогда и только тогда, когда $p$ является делителем $x$. Поэтому, поскольку $q$ является делителем $2^{q-1} - 1$, $p$ является делителем $q - 1$, так что $q \equiv 1 \pmod{p}$. Кроме того, поскольку $q$ является делителем $2^p - 1$, который является нечетным, $q$ является нечетным. Следовательно, $q \equiv 1 \pmod{2p}$. Этот факт приводит к доказательству теоремы Евклида, которая утверждает бесконечность простых чисел, отличных от доказательства, написанного Евклидом: для каждого нечетного простого числа $p$, все простые числа, делящие $2^p - 1$, больше, чем $p$; таким образом, всегда есть простые числа, больше, чем любое конкретное число. Из этого следует, что для каждого простого $p > 2$ существует по крайней мере одно простое число вида $2kp+1$ меньше или равно $M_p$, для некоторого целого $k$. Если $p$ является нечетным простым числом, то каждое простое $q$, делящее $2^p - 1$, сравнимо с $\pm 1 \pmod{8}$. Доказательство: $2^{p+1} \equiv 2 \pmod{q}$, так что $2$ является квадратным корнем из $2$ по модулю $q$. По теореме о квадратичной взаимности, каждое простое число, в котором число $2$ имеет квадратный корень, сравнимо с $\pm 1 \pmod{8}$. Число Мерсена не может быть числом Вифериха. Доказательство: Мы покажем, что если $M_p$ является числом Мерсена, то сравнение $2^{p-1} \equiv 1 \pmod{p^2}$ не выполняется. По малой теореме Ферма, $2^{p-1} \equiv 1 \pmod{p}$. Следовательно, можно записать $2^{p-1} = 1 + kp$ для некоторого целого $k$. Если данное сравнение выполняется, то $kp \equiv 0 \pmod{p^2}$, следовательно, $k \equiv 0 \pmod{p}$. Таким образом, $k = lp$ для некоторого целого $l$, и следовательно, $2^{p-1} = 1 + lp^2$. Это приводит к $p-1 \ge 2$, что невозможно, поскольку $p \ge 2$. Если $m$ и $n$ – натуральные числа, то $m$ и $n$ являются взаимно простыми, если и только если $2^m - 1$ и $2^n - 1$ являются взаимно простыми. Следовательно, простое число делит максимум одно число Мерсена с простым показателем. То есть, множество вредных чисел Мерсена является попарно взаимно простыми. Если $p$ и $2p + 1$ оба простые числа (что означает, что $p$ – простое число Софи Жермен), и $p$ сравнимо с $3 \pmod{4}$, то $2p + 1$ делит $2^p - 1$. Пример: $11$ и $23$ оба простые числа, и $23$ делит $2^{11} - 1$. Доказательство: Пусть $q = 2p + 1$. По малой теореме Ферма, $2^{2p} \equiv 1 \pmod{q}$, так что либо $2^p \equiv 1 \pmod{q}$, либо $2^p \equiv -1 \pmod{q}$. Предположим, что последнее верно, тогда $-2$ является квадратичным остатком по модулю $q$. Однако, поскольку $p$ сравнимо с $3 \pmod{4}$, $q$ сравнимо с $7 \pmod{8}$ и, следовательно, $2$ является квадратичным остатком по модулю $q$. Также, поскольку $q$ сравнимо с $3 \pmod{4}$, $-1$ является квадратичным невычетом по модулю $q$, поэтому $-2$ является произведением вычета и невычета и, следовательно, это невычет, что является противоречием. Следовательно, предыдущая конгруенция должна быть истинной, и $2p + 1$ делит $M_p$. Все составные делители чисел Мерсена с простым показателем являются сильными псевдопростыми числами по основанию $2$. За исключением $1$, число Мерсена не может быть совершенной степенью. То есть, и в соответствии с теоремой Михайлеску, уравнение $a^x + b^y = c^z$ не имеет решений, где $m, n$ и $k$ – целые числа с $m > 1$ и $k > 1$.

If a and p are natural numbers such that a^(p) − 1 is prime, then or Proof: a ≡ 1 ([[Modular arithmetic. Then a^(p) ≡ 1 (mod a − 1), so a^(p) − 1 ≡ 0 (mod a − 1). Thus However, a^(p) − 1 is prime, so or In the former case, , hence (which is a contradiction, as neither −1 nor 0 is prime) or In the latter case, or If , however, which is not prime. Therefore, If 2^(p) − 1 is prime, then p is prime. Proof: Suppose that p is composite, hence can be written with a and b > 1. Then 2^(p) − 1 so 2^(p) − 1 is composite. By contraposition, if 2^(p) − 1 is prime then p is prime. If p is an odd prime, then every prime q that divides 2^(p) − 1 must be 1 plus a multiple of 2p. This holds even when 2^(p) − 1 is prime. For example, is prime, and A composite example is , where and Proof: By Fermat's little theorem, q is a factor of 2^(q−1) − 1. Since q is a factor of 2^(p) − 1, for all positive integers c, q is also a factor of 2^(pc) − 1. Since p is prime and q is not a factor of 21 − 1, p is also the smallest positive integer x such that q is a factor of 2^(x) − 1. As a result, for all positive integers x, q is a factor of 2^(x) − 1 if and only if p is a factor of x. Therefore, since q is a factor of 2^(q−1) − 1, p is a factor of q − 1 so q ≡ 1 (mod p). Furthermore, since q is a factor of 2^(p) − 1, which is odd, q is odd. Therefore, q ≡ 1 (mod 2p). This fact leads to a proof of Euclid's theorem, which asserts the infinitude of primes, distinct from the proof written by Euclid: for every odd prime p, all primes dividing 2^(p) − 1 are larger than p; thus there are always larger primes than any particular prime. It follows from this fact that for every prime p > 2, there is at least one prime of the form 2kp+1 less than or equal to Mp, for some integer k.
If p is an odd prime, then every prime q that divides 2^(p) − 1 is congruent to ±1 (mod 8). Proof: 2^(p+1) ≡ 2 (mod q), so is a square root of 2 mod q. By quadratic reciprocity, every prime modulus in which the number 2 has a square root is congruent to ±1 (mod 8). A Mersenne prime cannot be a Wieferich prime. Proof: We show if is a Mersenne prime, then the congruence 2^(p−1) ≡ 1 (mod p^(2)) does not hold. By Fermat's little theorem, Therefore, one can write If the given congruence is satisfied, then , therefore ≡ −λ mod (2^(m) − 1). Hence , and therefore λ ≥ 2^(m) − 1. This leads to p − 1 ≥ m(2^(m) − 1), which is impossible since m ≥ 2. If m and n are natural numbers then m and n are coprime if and only if 2^(m) − 1 and 2^(n) − 1 are coprime. Consequently, a prime number divides at most one prime exponent Mersenne number. That is, the set of pernicious Mersenne numbers is pairwise coprime. If p and 2p + 1 are both prime (meaning that p is a Sophie Germain prime), and p is congruent to 3 (mod 4), then 2p + 1 divides 2^(p) − 1. Example: 11 and 23 are both prime, and , so 23 divides 211 − 1. Proof: Let q be 2p + 1. By Fermat's little theorem, 2^(2p) ≡ 1 (mod q), so either 2^(p) ≡ 1 (mod q) or 2^(p) ≡ −1 (mod q). Supposing latter true, then , so −2 would be a quadratic residue mod q. However, since p is congruent to 3 (mod 4), q is congruent to 7 (mod 8) and therefore 2 is a quadratic residue mod q. Also since q is congruent to 3 (mod 4), −1 is a quadratic nonresidue mod q, so −2 is the product of a residue and a nonresidue and hence it is a nonresidue, which is a contradiction. Hence, the former congruence must be true and 2p + 1 divides Mp. All composite divisors of prime exponent Mersenne numbers are strong pseudoprimes to the base 2. With the exception of 1, a Mersenne number cannot be a perfect power. That is, and in accordance with Mihăilescu's theorem, the equation has no solutions where m, n, and k are integers with m > 1 and k > 1.

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

Поскольку они являются простыми числами, простые числа Мерсена делятся только на 1 и на себя. Однако не все числа Мерсена являются простыми числами Мерсена. Числа Мерсена являются очень хорошими тестовыми случаями для специального алгоритма просеивания числового поля, поэтому часто наибольшее число, которое было разложено на множители с помощью этого алгоритма, было числом Мерсена. По состоянию на 2019 год рекордсменом является число, которое было разложено на множители с использованием варианта специального сита числового поля, позволяющего разлагать несколько чисел одновременно. См. записи о факторизации целых чисел для получения ссылок на дополнительную информацию. Специальное сито числового поля может разлагать числа, имеющие более одного большого множителя. Если число имеет только один очень большой множитель, то другие алгоритмы могут разлагать большие числа, сначала находя малые множители, а затем выполняя тест на простоту кофактора. По состоянию на 2022 год наибольшее полностью разложенное число (с допустимыми вероятными простыми множителями) равно , где q — вероятное простое число, состоящее из 3 829 294 цифр. Оно было обнаружено участником GIMPS с ником "Funky Waddle". По состоянию на 2022 год число Мерсена M1277 является наименьшим составным числом Мерсена без известных множителей; оно не имеет простых множителей меньше 268 и крайне маловероятно, что имеет какие-либо множители меньше 1065 (~2216). В таблице ниже показаны разложения на множители первых 20 составных чисел Мерсена:
pMpФакторизация Mp11204723 × 8923838860747 × 17848129536870911233 × 1103 × 208937137438953471223 × 61631817741219902325555113367 × 164511353438796093022207431 × 9719 × 2099863471407374883553272351 × 4513 × 132645295390071992547409916361 × 69431 × 2039440159576460752303423487179951 × 3203431780337 (13 знаков)67147573952589676412927193707721 × 761838257287 (12 знаков)712361183241434822606847228479 × 48544121 × 212885833739444732965739290427391439 × 2298041 × 9361973132609 (13 знаков)796044629098073145873530872687 × 202029703 × 1113491139767 (13 знаков)83967140655691033397649407167 × 57912614113275649087721 (23 знака)9715845632502818708790067111447 × 13842607235828485645766393 (26 знаков)1012535301200459934064107517432339208719 (13 знаков) × 341117531003194129 (18 знаков)1031014120480189736256430072550183799 × 3976656429941438590393 (22 знака)109649037107316312041152511745988807 × 870035986098720987332873 (24 знака)1131038459371709926584401913391 × 23279 × 65993 × 1868569 × 1066818132868207 (16 знаков)131272225893536454145691647263 × 10350794431055162386718619237468234569 (38 знаков)

Since they are prime numbers, Mersenne primes are divisible only by 1 and themselves. However, not all Mersenne numbers are Mersenne primes. Mersenne numbers are very good test cases for the special number field sieve algorithm, so often the largest number factorized with this algorithm has been a Mersenne number. as of 2019, is the record holder, having been factored with a variant of the special number field sieve that allows the factorization of several numbers at once. See integer factorization records for links to more information. The special number field sieve can factorize numbers with more than one large factor. If a number has only one very large factor then other algorithms can factorize larger numbers by first finding small factors and then running a primality test on the cofactor. as of 2022, the largest completely factored number (with probable prime factors allowed) is , where q is a 3,829,294 digit probable prime. It was discovered by a GIMPS participant with nickname "Funky Waddle". as of 2022, the Mersenne number M1277 is the smallest composite Mersenne number with no known factors; it has no prime factors below 268, and is very unlikely to have any factors below 1065 (~2216). The table below shows factorizations for the first 20 composite Mersenne numbers
pMpFactorization of Mp11204723 × 8923838860747 × 178,48129536870911233 × 1,103 × 2,08937137438953471223 × 616,318,17741219902325555113,367 × 164,511,353438796093022207431 × 9,719 × 2,099,863471407374883553272,351 × 4,513 × 13,264,5295390071992547409916,361 × 69,431 × 20,394,40159576460752303423487179,951 × 3,203,431,780,337 (13 digits)67147573952589676412927193,707,721 × 761,838,257,287 (12 digits)712361183241434822606847228,479 × 48,544,121 × 212,885,833739444732965739290427391439 × 2,298,041 × 9,361,973,132,609 (13 digits)796044629098073145873530872,687 × 202,029,703 × 1,113,491,139,767 (13 digits)83967140655691 033397649407167 × 57,912,614,113,275,649,087,721 (23 digits)97158456325028 18708790067111,447 × 13,842,607,235,828,485,645,766,393 (26 digits)101253530120045 9934064107517,432,339,208,719 (13 digits) × 341,117,531,003,194,129 (18 digits)103101412048018 9736256430072,550,183,799 × 3,976,656,429,941,438,590,393 (22 digits)109649037107316 312041152511745,988,807 × 870,035,986,098,720,987,332,873 (24 digits)113103845937170 9926584401913,391 × 23,279 × 65,993 × 1,868,569 × 1,066,818,132,868,207 (16 digits)131272225893536 454145691647263 × 10,350,794,431,055,162,386,718,619,237,468,234,569 (38 digits)

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

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

В математической задаче «Башня Ханой» решение головоломки с башней из n дисков требует Mn шагов, при условии отсутствия ошибок. Количество рисовых зерен на всей шахматной доске в задаче о пшенице и шахматной доске равно M64. Астероид с малым планетарным номером 8191 назван 8191 Мерсенн в честь Марина Мерсенна, поскольку 8191 является числом Мерсенна (3 Юнона, 7 Ирида, 31 Эвфросина и 127 Иоганна были открыты и названы в XIX веке). В геометрии примитивный прямоугольный треугольник с целыми сторонами, у которого четная сторона является степенью 2 (≥ 4), порождает уникальный прямоугольный треугольник, радиус вписанной окружности которого всегда является числом Мерсенна. Например, если четная сторона равна 2^(n + 1), то, поскольку треугольник примитивный, это ограничивает нечетную сторону значением 4^(n) − 1, гипотенузу значением 4^(n) + 1, а радиус вписанной окружности значением 2^(n) − 1.

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

Число Мерсена — Ферма определяется как 2p + rp, где p — простое число, r — натуральное число, и может быть записано как MF(p, r). Когда r = 1, это число Мерсена. Когда r = 2, это число Ферма. Единственными известными простыми числами Мерсена — Ферма с r > 1 являются MF(2, 2), MF(2, 3), MF(2, 4), MF(2, 5), MF(3, 2), MF(3, 3), MF(7, 2) и MF(59, 2). Фактически, MF(p, r) = Φp(r), где Φ — циклотомный полином.

Обобщения

Самые простые обобщенные простые числа Мерсена — это простые числа вида f(2^n), где f(x) — многочлен малой степени с небольшими целочисленными коэффициентами. Примером является 2^64 − 2^32 + 1, в этом случае, и ; другим примером является 2^192 − 2^64 − 1, в этом случае, и . Также естественно попытаться обобщить простые числа вида 2^n − 1 на простые числа вида b^n − 1 (при b ≠ 2 и n > 1). Однако (см. также теоремы выше), b^n − 1 всегда делится на b − 1, поэтому, если последнее не является единицей, первое не является простым числом. Это можно исправить, допустив, чтобы b было алгебраическим целым числом, а не целым числом.

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

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