Large Primes and Mersenne Primes

In the last two months, two new Mersenne Primes have been discovered. Mersenne Primes are prime numbers that are 1 less than a power of 2. So for example, 7 is a Mersenne prime. These two new primes 2^43,112,609-1 and 2^37,156,667-1 are the 45^th and 46^th Mersenne primes known and are the two largest primes known. Their discovery has made it into the popular press and has prompted multiple people to ask me what the big deal is and why mathematicians care about big primes anyways. This blog entry will be the first of three entries in which I will attempt to discuss these issues.

First, note that there are infinitely many prime numbers. This has been known since the ancient Greeks. An elegant proof is given by Euclid which I sketch out here: Assume I have a finite list of primes, p₁, p₂, p₃….p_n .If I take their product and add 1 I get p₁p₂p₃….p_n +1 and this number is clearly not divisible by any of the primes on my list. If this number is prime then I have a new prime that was not on my list. If this number is not prime then its smallest divisor that is not 1 must be a prime not on this list. Thus, for any finite list of primes I can always construct a new prime not on the list. There is a common misconception that if one takes , p₁, p₂, p₃….p_n to be the first n primes then it p₁p₂p₃….p_n +1 must itself be a prime. The smallest one where it does not lead to a prime is 2*3*5*7*11*13+1=59*509.

Unlike with generic primes, no one knows if there are infinitely many Mersenne primes. It is strongly believed that there are infinitely many but there is no proof as of yet. Mersenne primes are independently interesting for a variety of reasons. First, there is the issue of whether or not there are infinitely many. Second, Mersenne primes correspond to even perfect numbers. A number is said to be perfect if you add up all the positive divisors less than the number and end up with the number. So for example 6=1+2+3 so 6 is perfect. Euclid showed that for every Mersenne prime you could construct an even perfect number from it. Euler showed that the only even perfect numbers are those from Euclid's construction. Thus, information about Mersenne primes is information about perfect numbers, and discovering a new Mersenne prime leads to a new perfect number. I will discuss this in more detail in my next blog entry on this subject.

Third, Mersenne primes are interesting because there are tricks to test whether a number of the form 2^n-1 is prime that make it much easier to check whether such numbers are prime than a generic number. Thus, for most of the last 100 years the largest primes known have been Mersenne primes.

Now, why do we care about finding large primes? One simple reason is for the same reason that scientists might try to construct larger and larger atoms or might look for new species; because they are there, learning is fun, and you don't know what you might find.

Also, in a more general setting primes (although generally primes much smaller than Mersenne primes) are useful for cryptography which are used in many modern software applications. Many readers have likely used those cryptographic protocols without even realizing it when you've logged onto to secure websites and such.

Modern browsers handle the procedures for you automatically. So the ability to find large primes and related procedures (such as theability to factor large numbers quickly) are very relevant to the functioning of the modern economy as well as to various national security issues. I will discuss this cryptographic use of large primes in the third blog entry in this series.