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^{n}-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,

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^{n}-1)(2^{n-1}) where 2^{n}-1 is a Mersenne prime. For example, 6= 2*3 = (2^{2}-1)2^{1} and 28=7*4 = (2^{3}-1)2^{2}. That numbers of this form are perfect was proven by

First we need a small lemma:

Lemma 1: 1+2+4+8…+2^{n} = 2^{n+1}-1.

Proof: Consider S=1+2+4 + 8…+ 2^{n}. Then 2S=2+4+8…+2^{n+1} = S - 1 + 2^{n+1}. So

2S=S - 1 + 2^{n+1} 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 ^{n}-1)(2^{n-1}) with 2^{n}-1 is a perfect number.

Proof: The proof isn’t anything that complicated in modern notation. ^{n}-1)(2^{n-1}) and note that they are precisely N. Divisors of N take two forms, they either have a 2^{n}-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^{n}-1 by our previous lemma. Then there are the divisors that do contain a factor of 2^{n}-1. Those divisors are all of the form (2^{n}-1)2^{k}. For those divisors we get 1*(2^{n}-1) +2(2^{n}-1) 4*(2^{n}-1) ... + 2^{n-2} = (2^{n}-1) (1+2+4+8…+2^{n-2}) =

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

The proof of Euler’s result (that every even perfect number is of

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_{1}b_{1} where a_{1} divides a and b_{1} divides b. Moreover, since a and b are relatively prime this representation is unique. Thus, σ(ab)= (1+d_{1} + d_{2}… + d_{k}) = (1+a_{1}+a_{2}..+a_{m})(1+b_{1}+b_{2}…+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^{n}-1)(2^{n-1}) where 2^{n}-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^{n}-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-2}y +x^{m-3}y^{2}… 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^{11}-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^{300}) 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.

## 2 comments:

Heyas,

Where's the third part, I couldn't find it.

http://religionsetspolitics.blogspot.com/2008/11/diffie-hellman-how-to-share-secret-with.html is part 3

Post a Comment