Lucas Lehmer test

Largest Known Prime Number has been updated

Manjil Saikia

Jan 9, 2018 • 3 min read

The Great Internet Mersenne Prime Search (GIMPS) has announced recently that it has discovered a new prime number, which is also the largest known prime number right now. The number is $2^{77232917}-1$ , which has 23,249,425 digits, and was discovered in December 2017. This number is nearly one million digits longer than the previous largest known prime, discovered in 2016. This number belongs to the class of primes known as Mersenne primes, named after a French monk Marin Mersenne, which are primes of the form $M_p=2^p-1$ , where $p$ is also a prime.

GIMPS is a collaborative effort where individuals can download the GIMPS software which looks for Mersenne primes using their computer’s idle time. There is also a research discovery prize for individuals whose computers discover massive primes using the GIMPS software. The latest prime was found by the computer owned by Jonathan Pace, who is now eligible for the 3000 dollars prize.

Prime numbers are the building blocks of all integers and are quite rare and gets rarer as one goes up higher in the number line. There can be no largest prime number, as one of the first results in number theory says that the number of primes are infinite. But, for mathematicians the discovery of a previously unknown prime number is a rare event and one that also calls for celebrations. Primes are very useful in numerous activities in the current age. Having a handy reference of large primes is essential for many cryptographic activities.

It might seem surprising that the latest known primes are all Mersenne primes. However, once one knows how to look for such primes then it becomes clear that looking for Mersenne primes is a good bet to find new primes. The test which is usually employed in this case to decide whether the Mersenne number is a prime or not is called the Lucas-Lehmer test. Initially Mersenne believed that any number of the form $M_p$ are primes, but he was wrong as the lowest counterexample would be $$M_{61}$$ which is not a prime.

The Lucas-Lehmer test was first discovered by E. Lucas in 1856, and improved subsequently by Lucas in 1878 and Lehmer in 1930s. The test is quite simple and is as follows: Let $M_p$ be a Mersenne prime to be tested with $p$ , an odd prime. We then define a sequence $s_i$ , where $s_0=4$ and other $s_i$ ‘s are defined recursively as $s_i=s_{i-1}^2-2$ . Now, $M_p$ is prime if and only if $s_{p-2}$ is completely divisible by $M_p$ . The proof that this really works would be a bit more involved and is left for another time.

Another interesting observation here would be that, every time a new Mersenne prime is discovered, we also get a new even perfect number. The numbers whose proper divisors sum up to the number itself are called perfect numbers, like 6, 24, etc. It is known for many centuries and is a classical result of Euclid-Euler that any even perfect number is of the form $2^{n-1}M_n$ , where $M_n$ is a Mersenne prime. An outstanding unsolved problem in number theory is to determine whether there exists any odd perfect number or not?

Sign up for more like this.