New Largest Prime Number Found

The largest known prime has now been bumped up. The recently discovered prime is 2^43112609 − 1 which in base 10 has around twelve million digits. As with all the largest primes discovered for most of the last hundred years, the prime is a Mersenne prime, that is it is one less than a power of 2. As with the last few Mersenne primes discovered, this was discovered by the Great Internet Mersenne Prime Search which uses distributed computing to search for Mersenne primes. I've blogged before about Mersenne primes. For more details on why we care about Mersenne primes and their history dating back to the ancient Greeks see this post and this post.

There are reasons to suspect that if 2^n-1 is prime that n-1 should be likely to have a lot of small prime factors. In this case, 43112609 -1= 2^5 * 7 * 11 * 17497. So while some of the prime divisors look very small, it has at least one prime very large prime divisor and so doesn't seem to fit this pattern well. This is in contrast to the last discovered Mersenne prime 2^42643801 - 1. In that case one has 42643800 = 2^3 * 3^3 * 5^2 * 53 * 149. It remains to be seen if this new example is simply an outlier or if we need to reevaluate what we expect the exponents of Mersenne primes to look like.

New Mersenne Prime Found

Mersenne Primes are primes that are one less than a power of 2. Small examples are 7 (one less than 8) and 31 (one less than 32). I've blogged before about Mersenne primes here and here. To recap, each Mersenne primes corresponds to an even perfect number. It is unknown whether there are infinitely many Mersenne primes. However, we do understand them well enough that we have a very fast test for whether a Mersenne number (a number one less than a power of 2) is prime. Thus, the largest primes known are generally Mersenne prime.

The newest Mersenne Prime is 2^42643801 - 1. This is in fact not the largest prime discovered because it is actually smaller than the previously discovered Mersenne prime. This prime, like most of the other Mersenne primes recently discovered, was discovered by the Great Internet Mersenne Prime Search. This project uses a distributed computing system to search for Mersenne primes. Volunteerrs install the GIMPS software on their machines and the program runs in the background, quietly searching for Mersenne primes. The program is set up to only use processing power that the computer is not otherwise using. Thus, the program has no negative impact on performance. This is another example of the triumphs of modern technology and mathematics.

One other thing to note: There are technical reasons to suspect that 2^n-1 will be more likely to be prime when n-1 has a lot of small prime factors. In this case, 42643800 factors into 2^3 * 3^3 * 5^2 * 53 * 149 so n-1 does in fact have many small prime factors in this example.

Failure of Unique Prime Factorization

In an earlier entry I discussed Unique Prime Factorization and the ancient Greeks. Some systems very similar to the integers have unique prime factorization while others do not. Let's look at some of those systems.

Consider the Gaussian integers, normally denoted Z[i]. Z[i] is the set of all complex numbers of the form a+bi where a and b are integers and is the square root of negative one. It is not that hard to see that Z[i] is closed under both addition and multiplication. That is, if I take two elements in Z[i] and take their product or sum then the result is also in Z[i]. Furthermore, every element in Z[i] has an additive inverse, that is a number to which I can add to it to get 0. For any a+bi this is just -a-bi. Multiplication and addition are both associative and commutative, and multiplication distributes over addition. Thus, Z[i] is very similar to Z, the set of integers. Sets which satisfy these properties are called rings and are generally symbolized with bold letters. It turns out that rings are the natural setting to look for unique prime factorization.

At first glance, it might seem that the Gaussian integers do not have unique prime factorization. For example, (1+2i)(1-2i)=5=(2-i)(2+i). However, this can be easily corrected. What we have done is something sneaky called multiplying by a unit. In the integers we can do this also. (-3)(-5)=3*5. This isn't because unique prime factorization breaks down. We can always multiply terms by some product of numbers that equal 1. In the case in Z, we used -1 and -1. In the case with (1+2i)(1-2i) we used i and -i. Numbers in a ring which divide 1 are called units. Thus, for example if we were in R, the set of real numbers, every non-zero number is a unit since for any x, we can multiply it by 1/x to get 1. In the integers, the only units are 1 and -1. It turns out that the Gaussian integers have a total of 4 units, -1,1, i and -i. Factorization in the Gaussian integers is unique up to multiplication by units just as factorization in the integers is unique up to multiplication by units.

In the early part of the 19th century it was taken for granted that all well-behaved rings had unique prime factorization. However, this turns out to be false. The standard counterexample is A, the set of numbers of the form a+bk where k is the square root of -5. Like the Gaussian integers, A forms a ring. Unlike the Gaussian integers, A does not have unique prime factorization. We have 2*3=6 and (1+k)(1-k)=1-k+k+k^2=1+5=6. 2,3, 1+k and 1-k cannot be broken down further in any useful way. Thus unique prime factorization fails. The failure of unique prime factorization turns out to be deeply linked with a number of serious issues. In particular, the lack of unique prime factorization in general rings was the major reason that mathematicians in the 19th century were unable to prove Fermat's Last Theorem.

Although A is the standard example of unique prime factorization failing, it isn't a very satisfying example. It isn't clear why unique prime factorization is failing and it isn't clear that if one were looking for an example ring where unique prime factorization fails that one would construct A. There is a slightly more abstract ring that does the job a bit better. Consider the ring B = R[a,b,c,d]/(ab-cd). What we mean by this ring is to take all the products and sums of four formal symbols, a,b,c,d and all real numbers. Thus we would have for example 2a+b as an element. By /(ab-cd) we mean to treat ab-cd as zero. Thus, we do arithmetic formally on this set of four symbols, but we may whenever we see ab or cd replace it by the other. Now, this set is a ring. And it clearly fails at unique prime factorization. Just look at ab and cd. They are different prime factorizations for ab. Unlike with A, there's no difficulty involved in showing that the numbers in question are somehow genuinely behaving like primes. It is immediately obvious from the construction that there is no way of representing a,b,c, or d as an interesting product of terms.

It isn't clear to me why this example isn't used more often. Although it is more abstract than A, the failure of unique factorization is much clearer.

Euclid, Unique Prime Factorization and Sapir-Whorf

Unique prime factorization is a basic fact about the positive integers that many of us learn from a young age. Start with any positive integer and express it is as a product of prime numbers, say 105=3*5*7. This prime factorization is unique. That is to say, except for rearranging the order of these primes, there is no other way to express 105 as a product of prime numbers. Thus, for example, I don’t need to do any calculations to know that 105 is not equal to 11 *13. We can do this for any positive integer and regardless of what integer we start with we will get a unique result. (Another way of stating this is that if two people are both given the same number and told to factor it into primes, they will always get the same result as each other).

This idea is often called the "Fundamental Theorem of Arithmetic." Unique factorization is taught to children as young as 6th grade. When I have helped to teach number theory to high school students at PROMYS, many students take unique prime factorization for granted. Indeed, it often takes effort to convince them that the statement needs to be proved and is not just an obvious fact.

Despite the “obviousness” of unique prime factorization to the modern mind, the ancient Greeks did not know about unique prime factorization. This apparent failure of the ancient Greeks is well known to historians

of mathematics, but not known by many mathematicians. The only math text I am aware of which mentions this is Hardy and Wright's “Introduction to the Theory of Numbers. Euclid in his seminal work “The Elements” has many results that are close to unique prime factorization. For example, Euclid was able to show that, if a is relatively prime to b and relatively prime to c, then a is relatively prime the produc of b and c. This result is almost as powerful as unique prime factorization, but it is not all the way there.

Why did the ancient Greeks not have this result? Simply put, they lacked the words to express the statement. To a mathematician of ancient Greece, there was no way to say "take a bunch of numbers and take their product." A product of two numbers x and y was easy; it was the area of a rectangle with sides of length x and y. Similarly, a product of three numbers -- x, y and z -- was the volume of a box with side lengths x,y and z. Fixed in this geometric mindset and with no concept of higher dimensions, the ancient Greeks could not talk about general products. Being unable to talk about general products, they apparently did not think about them.

To be sure, they groped towards this result. For example, Euclid proved a result that in modern language would be stated as follows: if n is the least positive integer divisible by some list of distinct primes p₁,p₂.p₃… p_k, then n is not divisible by any prime not on the list. This result is trivial if one knows that prime factorization is unique this is obvious since one can simply has n=p₁ * p₂... *p_k.

Apparently, the ancient Greeks, including Archimedes, Euclid and Diophantus, along with many lesser luminaries could not conceive of this idea because they lacked the language to express it. This failure is closely related to a hypothesis in psychology and linguistics known as the Sapir-Whorf hypothesis. Sapir-Whorf states that our language constrains our thought processes. There are different degrees of Sapir-Whorf. Very strong versions of the hypothesis are obviously false (if they were to be believed, translation between languages would be impossible) while very weak versions border on the trivial. This failure of the ancient Greeks is evidence for some strong form of Sapir-Whorf.

There's a lesson here for people other than psychologists. We cannot know how much we are missing simply because we lack the language to express an idea. Mathematicians over the last three centuries have taken this idea very seriously and spent much time trying to find optimal notation to express ideas. Yet, we cannot tell if there is some fundamental idea that we simply do not notice or appreciate because we lack the necessary language.

Diffie-Hellman: How to share a secret with everyone listening.

This post is the third post of a series of three posts on why we care about prime numbers. The first entry gave an overview of primes. The second discussed the link between Mersenne primes and perfect numbers. This post will discuss practical applications of large prime numbers and provide a concrete example.

The main focus of this post is the Diffie-Hellman algorithm. Diffie-Hellman is a procedure whereby two people can have a conversation and at the end of the conversation they will share a secret number. The remarkable thing is that even if an eavesdropper hears the entire conversation, the eavesdropper will have no feasible way of figuring out the secret. . By repeating this procedure many times two people develop can have a list of secret numbers which they can use to encrypt messages to each other that only they can read. As is standard in cryptography, I will refer to three people, Alice and Bob who want to share a secret number and Eve the evil eavesdropper wishes to obtain their secret number.

There is a standard analogy in cryptographic circles to accomplish this sort of task. Suppose Alice and Bob want to exchange an object through a mail system that they don't trust. But they know the mail employees aren't going to be able to get into a locked box. How can Alice send an object to Bob? She cannot just send a locked box because Bob won't have a key. Nor can she send a box and a key because then the corrupt mailmen can use the key to open the box. Here is the solution: Alice puts her object into the box and locks it with her lock. She mails this to Bob. Bob puts a second lock on the box and mails it back to Alice. Alice now removes her lock and sends it back to Bob. Bob can now remove his own lock and gain access to the contents of the box.

Before we discuss this algorithm in detail we need a few small mathematical facts. We call doing arithmetic where we only care about the remainder when divided by k to be “arithmetic mod k”. So for example, 4+6= 3 mod 7 since 4+6 = 10 and the remainder of 10 when divided by 7 is 3. For a concrete analog, when we tell what time it will be on a clock some number of hours from now we are doing arithmetic mod 12.

Now, we need to define a primitive root: Suppose for a fixed prime p we have some u such that u¹ u² u³ u⁴… u^p-1 mod p cycle through 1,2,3,4… p-1 in some order then we say that u is a primitive root for p. For example, if p=5, then 2 is a primitive root for 5 since 2¹=2,2²=4,2³=3,2⁴=1. But 4 is not a primitive root for 5 since 4¹=4, 4²=1,4³=4,4⁴=1 so we only cycled through 1 and 4. Now, it happens that every prime p has some primitive root u. The proof will not be given here but this fact is the only piece of non-trivial number theory we will need for this procedure.[1]

The last detail we need is to note how it is possible to quickly raises numbers to large powers. Naively, if I want to calculate xⁿ for some fixed x and large integer n I need to multiply by x n times. And this applies if I am operating mod k also. But we have a nice trick called repeated squaring that allows us to get around this. Observe that if we know x^y then we can calculate x^2y by squaring x^y. Thus, we can easily calculate x², x⁴, x⁸, x¹⁶ all the way up to the largest power of 2 less than n. Then we can write n in base 2 and calculate x^y in the obvious fashion by multiplying together the relevant powers of the form x^{2^t}. Thus, calculating xⁿ takes at most c log n multiplications for some fixed constant c.

We are now ready to outline the procedure. Alice says to Bob: Hey Bob, I want to talk to you. Let’s use Diffie-Hellman. Bob says ok and picks a large prime p (by large probably in the order of 100s of decimal digits) and Bob finds a primitive root u for this prime. Bob then picks a random positive integer between 1 and p-1, call it b. Bob calculates B = u^b mod p which is easy to calculate by our above remark. Bob then transmits B, p and u to Alice. Alice picks some a and calculates A = u^a mod p and sends A to Bob. Alice calculates S = B^a = (u^b)^a = u^ab mod p and Bob calculates by taking A^b mod p. Alice and Bob now share S. However, suppose we have our evil eavesdropper Eve. What information does she have? She has A. She has B. She has u and she has p. There’s no obvious way for Eve to work out u^ab mod p. If Eve had a fast way of finding a or b from knowing u^a=A mod p she’d be set. But that turns out to be quite hard. This problem, known as the discrete log, is very difficult in general. So Eve is stuck. Alice and Bob can construct an agreed upon code by repeatedly using this procedure and there’s nothing Eve can do about it. If Alice and Bob set p to be a few hundred digits than the computation necessary for Eve to work out what S is turns out to be more than all the computational power on Earth today.

Let's do a small example with Say p=17 and u=3. Bob says "My prime is 17, my primitive root is 3." Bob picks 6 as his random number. Bob calculates that 3⁶ mod 17 which is 15. So he says "my B is 15."

Alice picks a random number, say 13 and calculates 3¹³ mod 17 which is 12 so she says "My A is 12.".

Bob then calculates A^b mod 17, which is 12⁶ mod 17 which is 2. Alice calculates B^a mod 17 which is 15¹³ mod 17 which is 2

So Alice and Bob now share the secret number S = 2. Obviously, for 17 it isn’t that hard for Eve to work out the answer. She just needs to write out a table of powers of 3 mod 17. But if instead of 17 she had to deal with a prime that was a few hundred digits long that strategy would never work; Eve's table would have more entries in it than the number of atoms in the universe. There are other strategies Eve could try to attack this but in general she doesn’t have many options.

An important caveat: No one knows a quick way of doing the discrete log but it has not yet been proven that there is no quick way to do so. Almost everyone who has studied the problem is very sure that there isn’t a quick way.

Diffie-Hellman turns out to have a variety of practical problems with implementation. So more often a related algorithm called RSA is used instead. In a later post, I will discuss RSA. RSA has even more counter-intuitive properties than Diffie-Hellman. While Diffie-Hellman required Alice and Bob to be work with each other, in RSA the intended recipient simply needs to publish a key which can then be used by anyone to encrypt messages such that only the recipient can read them. The standard analogy used by cryptographers to describe this procedure of a box that anyone is able to lock but only the person with a special key can unlock. The fact that this is mathematically doable turns out to be very useful. Readers have likely used RSA without even realizing it if they have engaged in almost any form of commerce over the internet. Modern web browsers and other software implement RSA in a way that is invisible to casual user. Even though one does not notice it RSA is responsible for keeping credit card numbers and similar data to safe and secure.

Both Diffie-Hellman and RSA rest heavily on the ability to find large primes. Moreover, the security of these algorithms is connected strongly to our understanding of prime numbers and their properties. Thus, the mathematics of large primes is vital to the functioning of the modern economy.

Edit: Added the locked box analogy.

---

[1] In fact we won’t really need that fact other than that we need in the procedure access to a prime that has a primitive root and we want to know that there are large primes with this property. Since all primes have this property, so do all large primes.

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.

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.