Mersenne Primes and Perfect Numbers

This is the second part of a series of three posts about why people care about large prime numbers. The first part can be found here. This post will focus on primes that are of the form 2ⁿ-1. Such primes are generally called Mersenne primes.

The historical reason for caring about Mersenne primes is that they are related to perfect numbers. A positive integer n is said to be perfect if n is the sum of all its proper divisors. For example, 6 is perfect because 1+2+3=6 but 8 is not perfect since 1+2+4=7 and 7 is not equal to 8. Perfect numbers were first studied by the ancient Greeks and have been connected to various numerological ideas. For example, St. Augustine noted that the world was created in 6 days and 6 is a perfect number.

The first few perfect numbers are 6, 28, 496 and 8128. These were the only perfect numbers known to the ancients with the next one 33550336 not discovered until much later. Now, how are these numbers related to Mersenne primes? Well, it turns out that every even perfect number is associated with a Mersenne prime. More particularly, an even number is prime if and only if it is of the form (2ⁿ-1)(2^n-1) where 2ⁿ-1 is a Mersenne prime. For example, 6= 2*3 = (2²-1)2¹ and 28=7*4 = (2³-1)2². That numbers of this form are perfect was proven by Euclid about 2300 years ago. About 2000 years later, Euler proved that these were the only even numbers that were perfect.[1] The main aim of this post will be to sketch out Euclid’s and Euler’s proofs in modern notation and then to discuss a few other properties of Mersenne primes.

First we need a small lemma:

Lemma 1: 1+2+4+8…+2ⁿ = 2ⁿ⁺¹-1.

Proof: Consider S=1+2+4 + 8…+ 2ⁿ. Then 2S=2+4+8…+2ⁿ⁺¹ = S - 1 + 2ⁿ⁺¹. So

2S=S - 1 + 2ⁿ⁺¹ and solving for S now gives us the desired result. Readers who recall their high school algebra will note that this is just the proof for the sum of a finite geometric series in the specific case with the first as 1 and with each succeeding term as twice the previous.

Proposition: A number of Euclid’s form is a perfect number. That is (2ⁿ-1)(2^n-1) with 2ⁿ-1 is a perfect number.

Proof: The proof isn’t anything that complicated in modern notation. Euclid had to do this using highly geometric notation but we can use modern notation to do this easily. All we are going to do is take the sum of the proper divisors of N=(2ⁿ-1)(2^n-1) and note that they are precisely N. Divisors of N take two forms, they either have a 2ⁿ-1 in them or they do not. The proper divisors that do not have such a factor are precisely the powers of 2. 1+2+4+8…+2^n-1 = 2ⁿ-1 by our previous lemma. Then there are the divisors that do contain a factor of 2ⁿ-1. Those divisors are all of the form (2ⁿ-1)2^k. For those divisors we get 1*(2ⁿ-1) +2(2ⁿ-1) 4*(2ⁿ-1) ... + 2^n-2 = (2ⁿ-1) (1+2+4+8…+2^n-2) =

(2ⁿ-1)(2^n-1-1) by Lemma 1. So the sum of all the proper divisors is (2ⁿ-1)(2^n-1-1) + (2ⁿ-1) = (2ⁿ-1)(2^n-1) = N. And so we are done.

The proof of Euler’s result (that every even perfect number is of Euclid’s form) is more involved than than Euler’s proof but is not difficult. First a small notational change: Let σ(n) be the sum of the positive divisors of n. For example, σ(4)=1+2+4=7. Note that unlike are previous sums this includes the number itself. Observe that N is perfect if and only if σ(N)=2N. It turns out that for most purposes σ(n) is nicer to work with than the sum of the proper divisors which is of course σ(n)-n.

Lemma 2: σ is multiplicative. That is, σ(ab)= σ(a)σ(b) whenever a and b are relatively prime.[2]

Proof: Observe that for any divisor d of ab we can write d=a₁b₁ where a₁ divides a and b₁ divides b. Moreover, since a and b are relatively prime this representation is unique. Thus, σ(ab)= (1+d₁ + d₂… + d_k) = (1+a₁+a₂..+a_m)(1+b₁+b₂…+b_n)= σ(a)σ(b) since every d_i can is the product of some a_j and b_h. Q.E.D.

We also need one other function. Define h(n)= σ(n)/n.

Lemma 3:

1) h(n) equal to the sum of the reciprocals of the positive divisors of n.

2) Furthermore, h(n) is multiplicactive.

3) If a divides b a is less than b then h(a) is less than h(b).

The proof of this lemma will be left as an exercise to the reader.

Also, it is helpful to note that N is perfect if and only if h(N)=2. It turns out that for constructing a general theory h(n) is the function in that some sense matters the most.

Now we are ready to prove Euler’s result:

Proposition: If N is an even perfect number then we may write N = (2ⁿ-1)(2^n-1) where 2ⁿ-1 is prime.

Proof: Assume N is an even perfect number. We may write N as m2^k where m is odd. By our earlier remarks this means σ(m2^k) = 2m2^k = m2^k+1. Now, since m is odd it is certainly relatively prime to 2^k. So σ(m2^k) = σ(m)σ (2^k)= σ(m)(2^k+1-1) (by Lemma 1). So σ(m)(2^k+1-1)= m2^k+1. Now, 2^k+1-1 divides m2^k+1. Since 2^k+1 is a power of 2, we must have 2^k+1-1 divides m. Now, if m is not prime we must have h(m) >= 1 + 1/(2^k+1-1) + 1/d >>= 1 + 1/(2^k+1-1) for some non-trivial divisor d (see part 1 of Lemma 3 above). But then an easy calculation establishes that h(m2^k) > 2m2^k which is a contradiction. So m must be prime and we are done.

Throughout this blog post I have referred to Mersenne primes as primes of the form 2ⁿ-1. In fact, in order for such an integer to be prime one also needs that n is prime. If n=ab for some a,b>1 then we can use the factorization trick x^m-y^m =(x-y)(x^m-1 +x^m-2y +x^m-3y²… xy^m-2+y^m-1) to get 2^ab-1 = 2^ab-1^a = (2^b-1)(2^b(a-1) … +1). Thus, mathematicians talk about Mersenne numbers being numbers of the form 2^p-1 prime. Not all such numbers are prime. For example, 2¹¹-1 = 23*89. But it turns out that there are very quick ways of testing whether such numbers are prime. Those methods are beyond the scope of this blog post which is already becoming quite lengthy. However, I will say that those fast methods have resulted in Mersenne primes being the largest known primes for most of the last 100 years.

There is a distributed computing project searching for more such primes. The project, called “GIMPS” for Great Internet Mersenne Prime Search, has found most of the Mersenne primes found recently. That project allows you to download software which runs in the background and uses your computer’s spare processing power to search for Mersenne primes. Recently they discovered the 45^th and 46^th known Mersenne primes. These two numbers 2^43,112,609-1 and 2^37,156,667-1 are each in the range of 10 million decimal digits long. These are big numbers. I strongly urge readers to go download the software for GIMPS. It doesn’t cost anything, doesn’t take up your time and you might even find something interesting.

In this post I’ve laid out the historical basis and some of the intellectual basis for caring about large primes. In my next post in this series I will discuss practical reasons why people care about large primes. I’ll discuss how you can share a secret with someone without having to worry about eavesdroppers and how that is relies on prime numbers.

---

[1] The astute reader will note that we have switched from talking about perfect numbers in general to only talking about even perfect numbers. What about perfect numbers that are odd? The answer is that no one knows. There are many restrictions on what an odd perfect number must look like. Any odd perfect number must be very large (greater than 10³⁰⁰) and have at least 9 distinct prime factors. There are good reasons (especially those presented by Carl Pomerance) to believe that no such numbers exist. However, a proof is not in sight.

[2] If anyone suspects that I’m writing posts on this subject so I can talk about multiplicative functions which are some of my favorite functions, they may be right.