Số nguyên tố Mersenne

Marin Mersenne was a French Minim friar, music theorist and tireless correspondent who acted as a clearing house for European mathematics in the 1630s and 1640s. In Cogitata Physico-Mathematica (1644) he asserted that 2^p - 1 is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and composite for every other p below 257. He gave no proof, and he got it wrong in five places: 67 and 257 are composite, and he left out 61, 89 and 107. It took nearly three centuries to finish checking a single sentence.

Euler settled 2^31 - 1 in 1772. In 1876 Édouard Lucas proved 2^127 - 1 prime — thirty-nine digits, by hand, and still the largest prime ever found without a machine — and in the same work showed that Mersenne's 2^67 - 1 was composite without producing a factor. That loose end became one of mathematics' better anecdotes: at an American Mathematical Society meeting in New York in 1903, Frank Nelson Cole walked to the blackboard, silently worked out 2^67 - 1, then multiplied 193,707,721 by 761,838,257,287 to get the same number, and sat down to applause without having spoken. He later said the calculation had taken him "three years of Sundays".

Machines took over in 1952, when Raphael Robinson ran Lucas's test — sharpened into the Lucas–Lehmer test by Derrick Henry Lehmer around 1930 — on the SWAC computer in Los Angeles and found five new Mersenne primes in a single year. In 1996 George Woltman launched the Great Internet Mersenne Prime Search, and every Mersenne prime from the 35th onwards has come out of it. The 52nd and largest, 2^136,279,841 - 1, was reported in October 2024 by Luke Durant using rented GPU capacity: 41,024,320 digits.

Tính chất chính

• 2^n - 1 can only be prime when n is itself prime, because 2^ab - 1 is always divisible by 2^a - 1.
• The converse fails: 11 is prime but 2^11 - 1 = 2047 = 23 × 89.
• 52 Mersenne primes are known. Every exponent below the 48th (57,885,161) has been tested, so the first 48 are consecutive; gaps may remain between the larger ones.
• Euclid showed that 2^(p-1)(2^p - 1) is perfect whenever 2^p - 1 is prime; Euler proved the converse, so even perfect numbers and Mersenne primes are in exact correspondence.
• The Lucas–Lehmer test decides primality of 2^p - 1 for odd prime p by iterating s := s² - 2 modulo 2^p - 1, starting from s = 4; the number is prime exactly when the (p-2)th value is 0.
• If p is a prime congruent to 3 modulo 4 and 2p + 1 is also prime, then 2p + 1 divides 2^p - 1 — which is how 23 divides 2047.
• In binary a Mersenne prime is a string of p ones, making these the base-2 repunit primes.
• Nobody knows whether infinitely many Mersenne primes exist, nor whether infinitely many Mersenne numbers with prime exponent are composite.

Xuất hiện ở đâu

• 2^31 - 1 = 2,147,483,647 is the largest value a signed 32-bit integer can hold, which is why 32-bit Unix timestamps overflow in January 2038.
• The NIST P-521 elliptic curve is defined over the field of 2^521 - 1 elements — the 13th Mersenne prime, chosen because arithmetic modulo a Mersenne prime reduces to shifts and adds.
• The Mersenne Twister pseudorandom generator takes its name from its period, 2^19937 - 1, the 24th Mersenne prime.
• Lehmer's "minimal standard" random number generator, long the default in scientific libraries, works modulo 2^31 - 1.
• Even perfect numbers — 6, 28, 496, 8128 and so on — come one per Mersenne prime, so only 52 are known.
• GIMPS is one of the longest-running volunteer distributed computing projects, and collected the Electronic Frontier Foundation award for the first prime with ten million digits.