By Akshay Asija
Prime numbers are unique entities in a realm that is defined by patterns. These positive numbers, divisible only by themselves (besides 1), are introduced to most of us in grade school. The concept of prime numbers is easy to understand, but their occurrence among other numbers does not follow a well-defined scheme. This peculiarity has baffled humanity for a very long time, and while an established definition of prime numbers exists, a simple formula to separate them from composite numbers does not.
Mersenne Prime Numbers
One can check the primality (i.e. the property of being prime) of a given number by trying to fully divide it by each number that lies between its square root and 2. This process, called trial division, is accurate, but extremely slow and impractical for numbers with three or more digits. For finding larger prime numbers, several algorithms have been devised. These algorithms are much faster than any manual technique but occasionally give erroneous results. A few of these algorithms are used to compute Mersenne prime numbers.
A Mersenne prime is defined as a prime number that is one less than some multiple of two. 3 (which is one less than 2×2 = 4) is the smallest Mersenne prime number. These special prime numbers are named after Marin Mersenne, a medieval era French polymath who studied these in great detail. The simple nature of the Mersenne prime formula (Mn = 2n – 1) makes the formula particularly good for designing algorithms that compute Mersenne primes for larger values of the exponent (n). The Lucas-Lehmer primality test is one such algorithm.
A massive, collaborative project, called the Great Internet Mersenne Prime Search (GIMPS) is engaged in the search for Mersenne primes. Members of this project are volunteers who run Prime95, a freely available software on their computers to perform the Lucas–Lehmer primality test. In order to check the results’ primality, Prime95uses trial division to eliminate smaller Mersenne numbers and Pollard’s (p – 1) algorithm to search for larger factors. Prime95 (or mPrime, its Linux counterpart) work efficiently on binary computer architectures. A system software, called the PrimeNet, coordinates all the computers that are running the GIMPS software. As a result of the collaborative (and sometimes, even competitive) nature of the project, GIMPS and its members have been credited for finding a total of sixteen Mersenne primes, ever since the inception of the project in 1996.
The discovery of the largest Mersenne prime number
Last year, on December 26, Jonathan Pace, a 51-year old Electrical Engineer from Germantown, Tennessee discovered the largest known prime number. The number, 277,232,917 – 1, and also called the M77232917, is about 23.2 million digits long. Pace, who is immensely passionate about mathematics, first began searching for Mersenne primes more than 14 years ago, in 2003. At that time, he had read an article about the discovery of the 40th known Mersenne prime number and became interested in looking for more such numbers.
Today, he serves as a deacon at the Germantown Church of Christ in Tennessee, apart from his regular job at FedEx. Pace is the network administrator of the church and builds the desktops for them. On a few computers in the church, he has installed Prime95, and it was one of these computers that checked and verified the newest Mersenne prime. Computing the proof of the primality of M77232917 required 6 days of constant computing on the machine, which is equipped with an entry-level Intel Core i5-6600 CPU. A $3,000 GIMPS research discovery award has been announced by the GIMPS in recognition of his efforts. Pace, along with the GIMPS, now wants to discover the first prime number that contains 100 million digits, as its discoverer will receive a prize of $150,000 from the Electronic Frontiers Foundation. Similarly, the first 1 billion-digit prime is worth $250,000 of prizemoney.
The discovery of this new prime number was also independently verified by using four different programs on four different hardware configurations. Aaron Blosser, the system administrator of PrimeNet, verified it using Prime95 on an Intel Xeon server in 37 hours, while others used software like gpuOwl, CUDALucas, and Mlucas on other machines to confirm the finding.
What makes M77232917 special?
A text file that contains just M77232917, and nothing else, takes up about 23 megabytes of space on a computer, and the number is long enough to fill an entire shelf of books (about 9000 pages). It is the 50th known Mersenne prime and has 910,807 digits more than the previous largest known Mersenne prime. However, there may exist more Mersenne primes smaller than M77232917, since GIMPS has not dismissed the possibility of there being undiscovered primes between the 46th and the 50th Mersenne primes.
What makes this discovery even more interesting is that it has led to the discovery of a new perfect number. A perfect number is one that is equal to the sum of all its positive divisors (apart from the number itself). According to a theory postulated by the 18th-century mathematician Leonhard Euler, a number (say, k) is even and perfect if and only if it has the form 2n-1(2n-1) and 2n-1 is prime. In the case of M77232917, the corresponding perfect number, (2^77,232,917-1)x(2^77,232,917-1) is huge, with over 46 million digits.
The significance of prime numbers
Prime numbers are surrounded by an air of mystery. Many of the questions about these numbers, such as twin prime conjecture (that there are infinitely many pairs of primes whose difference is 2) remain unanswered. However, prime numbers are immensely useful, especially in information technology, where they are used for public-key cryptography. The difficulty of factoring large numbers into their prime factors is something that is exploited in this form of encryption. Prime numbers are also used in algebra, in the concepts of prime elements and prime ideals, among others.
Featured Image Source: Pixabay
Stay updated with all the insights.
Navigate news, 1 email day.
Subscribe to Qrius