May 22, 2009, was not a particularly special day for many people, but the world of mathematics received "good news": we have found the 47th Mersenne prime, which means 2^{42643801}-1 is a prime number! The new prime was verified on June 12 by Tony Reix from France. It is currently the second-largest known prime number, consisting of 12,837,064 digits! This was discovered through participation in an international cooperative project called the "Great Internet Mersenne Prime Search" (GIMPS). Let us look back at this journey of prime numbers together!
Primes / Mersenne Primes
Prime numbers are often referred to as "prime" in textbooks, though many mathematicians and enthusiasts still use the term "sushu" (prime) in Chinese (perhaps because the name sounds better). These refer to integers that cannot be decomposed into the product of two smaller integers, such as 2, 3, 5, 7, etc. Except for 2, all prime numbers are odd.
Two thousand years ago, the Pythagorean school of ancient Greece proposed an interesting type of number: a number where the sum of all its factors (excluding the number itself) equals the original number. These numbers are called "perfect numbers." For example, 6 = 1 + 2 + 3, where 1, 2, and 3 are all the factors of 6. Since then, these numbers have been passed down as an intriguing subject of study.
The great mathematician Euclid proposed a formula for constructing perfect numbers: 2^{p-1}(2^p-1), where 2^p-1 is a prime number. Euclid might not have imagined that this formula would lead to an enduring topic of interest: the search for Mersenne primes of the form 2^p-1. Of course, the first person to study this form of prime number independently was the mathematician Marin Mersenne, not Euclid. Today, finding a Mersenne prime is equivalent to finding a perfect number. This is because no odd perfect numbers have been discovered to date, and this is the only known form for even perfect numbers.
The Search Process
However, the journey of searching for Mersenne primes has not been smooth. It was discovered early on that for 2^p-1 to be prime, p itself must be a prime number. This is because if p is a composite number that can be written as p = ab, then 2^{ab}-1 = (2^a)^b-1 = (2^b)^a-1, which must contain factors 2^a-1 and 2^b-1.
But the converse of this theorem does not hold; that is, if p is prime, 2^p-1 is not necessarily prime. For example, 2^{11}-1 = 2047 = 23 \cdot 89. Even worse, such primes are extremely rare among natural numbers. By 1500, only five Mersenne primes had been discovered: p = 2, 3, 5, 7, 13.
Since then, famous mathematicians such as Fermat, Descartes, Leibniz, Euler, Goldbach, Lucas, Shanks, Cole, and Gillies have all conducted research on these primes. Marin Mersenne was one of the most prominent contributors, which is why primes of the form 2^p-1 were later named Mersenne primes in his honor.
Proof / Judgment
The Lucas-Lehmer primality test is currently the best-known method for testing the primality of Mersenne numbers. This method was discovered by Edouard Lucas in 1878 and improved by Lehmer in the 1930s, hence the name.
The method is based on the calculation of a recursive sequence. Its principle is: M_p is prime if and only if M_p divides S_{p-2} (where S_0 = 4 and S_k = S_{k-1}^2 - 2 for k > 0).
Suppose we want to verify that M_3 = 7 is prime. We start with s = 4 and update it 3-2 = 1 time, taking the result modulo 7:
s \leftarrow ((4 \times 4) - 2) \pmod{7} = 0
Since we ultimately obtained an s divisible by 7, M_3 is prime.
On the other hand, M_{11} = 2047 = 23 \times 89 is not prime. We still start with s = 4 and update it 11-2 = 9 times, taking all results modulo 2047:
s \leftarrow ((4
\times 4) - 2) \pmod{2047} = 14
s \leftarrow ((14
\times 14) - 2) \pmod{2047} = 194
s \leftarrow ((194
\times 194) - 2) \pmod{2047} = 788
s \leftarrow ((788
\times 788) - 2) \pmod{2047} = 701
s \leftarrow ((701
\times 701) - 2) \pmod{2047} = 119
s \leftarrow ((119
\times 119) - 2) \pmod{2047} = 1877
s \leftarrow ((119
\times 119) - 2) \pmod{2047} = 1877
s \leftarrow ((1877
\times 1877) - 2) \pmod{2047} = 240
s \leftarrow ((240
\times 240) - 2) \pmod{2047} = 282
s \leftarrow ((282
\times 282) - 2) \pmod{2047} = 1736
Since s is ultimately not divisible by 2047, M_{11} = 2047 is not prime. However, we still cannot determine the factors of 2047 from this test; we only know its Lucas-Lehmer remainder is 1736.
For M_p (where p is prime):
If a is a factor of M_p, then a has the following properties:
a \equiv 1 \pmod{2p}
a \equiv \pm 1 \pmod{8}
Search / Calculation
Mersenne primes seem simple, but researching them is very difficult. It requires not only profound theory and refined skills but also arduous calculations.
Between late 1995 and early 1996, American mathematician and programmer George Woltman developed a Mersenne prime calculation program and placed it on a website for free use by mathematicians and enthusiasts. This is the world-famous GIMPS project. The project uses a distributed computing approach, utilizing the idle resources of a large number of ordinary computers to achieve computing power equivalent to a supercomputer. The famous British journal Nature once reported that the GIMPS project would not only further stimulate enthusiasm for searching for Mersenne primes but also draw significant attention to the application of distributed computing. In 1997, American mathematician and programmer Scott Kurowski and others established "PrimeNet," which automated the distribution of search ranges and the reporting of results to GIMPS. Now, anyone can download a free program called Prime95 from the GIMPS homepage and immediately participate in the search for Mersenne primes.
www.mersenne.org - Official GIMPS Website
www.mersenneforum.org - Official GIMPS Forum
References:
When reposting, please include the original link: https://kexue.fm/archives/63
For more detailed information on reposting, please refer to: Scientific Space FAQ