Prime Numbers: Mersenne Primes Edition

Recall that a natural number is called prime if the only numbers which divide it evenly (ie. when you divide you get a remainder of 0) is 1 and the number itself.   The first few prime numbers are:

2,3,5,7,11,13,...

Mathematically, prime numbers are important because every natural number can be decomposed uniquely into a product of prime numbers:

n = p_{1}^{d_1} p_{2}^{d_2} \cdot \dotsb \cdot p_{k}^{d_k}.

Where p_1, p_2, \dotsc, p_k are prime numbers.  For example,

67914 = 2 \cdot 3^{2} \cdot 7^{3} \cdot 11.

So primes are the “atoms” of the natural numbers.

They are real-life useful as well.  The encryption used on webpages when you enter your credit card uses very, very large prime numbers.  What it uses is the fact that it’s easy to multiply large primes together, but it’s hard to take a very large number and break it down into its prime factors.

Recently the Great Internet Mersenne Prime Seach (GIMPS) announced that computers have verified that

2^{37,156,667}-1

2^{43,112,609}-1

are both prime numbers.  They are the first primes large enough to qualify for the $100,000 prize from the Electronic Frontier Foundation.  The prize is for the first prime with more than 10,000,000 digits and these primes have 11,185,272 and 12,978,189 digits, respectively.  If you would like to see the largest prime known to humankind, click hereWarning!  That link takes a long time to load, so only do it if you have a fast internet connection and lots of time on your hands!

More on Mersenne Primes below:

Marin Mersenne

A Mersenne Prime is a prime number of the form 2^{n}-1 for some natural number n. They were consider way, way back by Euclid, but were first seriously considered by Marin Mersenne in the 17th century.
He compiled a list of all the n = 1, 2, 3, \dotsc, 257 which give prime numbers.  No one is quite sure how he did such a massive calculation (2^{257}-1 has 78 digits!).  After 200 years mathematicians were able to verify his calculations and see that he was (mostly) correct!

Not all numbers of the form 2^{n}-1 are prime.  In fact, it is easy to see that if n can be factored, then so can 2^{n}-1.  You just use the factorization:

2^{ab} - 1 = (2^{a} - 1)(1+2^{a} + 2^{2a} + 2^{3a} + \dotsc + 2^{(b-1)a}).

However, just because n is a prime number doesn’t mean that 2^{n}-1 is prime.  For example, 2^{11}-1 is not a prime because it can be divided by numbers other than 1 and itself (Which ones?  That’s homework!).

Lots of things are still unknown about Mersenne primes.  For example, nobody knows if there is finitely many or infinitely many!  So far (counting the ones above) 45 Mersenne primes have been found so far.

If you’re interested in finding the next Mersenne prime, GIMPS is always looking for people to volunteer their computers to work on this problem in their free time.  If you’re lucky enough to find the next one, you’ll be famous and wealthy (the EFF is offering $150,000 to whomever discovers a prime number with more than 100,000,000 digits and $250,000 for the first prime with more than 1,000,000,000 digits).

If you would like to buy a poster of showing one (only one can be squeezed onto a poster!) Mersenne prime, you can get them here.  They are supposed to offer a poster with the newest primes in the near future.

Addendum: Today Terence Tao, Fields Medalist and UCLA faculty member, has a post on his blog where he talks about the math used by the GIMPS project to test if a Mersenne number is actually prime.  You can check it out here.  Note:  UCLA computers were used to find one of the new primes.

About these ads

14 thoughts on “Prime Numbers: Mersenne Primes Edition

  1. I think it’s amazing that these two primes have been found so close together in time. I’ve been a member of GIMPS for over a year now, and I’ve tested fewer than a score of exponents; they aren’t kidding when they say you need patience to run the software. Way to go, GIMPS for finding these numbers.

    The concept of distributed computing has always interested me, and the virtual supercomputers that these projects make are truly mind blowing: GIMPS reports 28 Trillion floating point operations per second (28 terra-FLOPS). If you want to join a group like this, GIMPS is fairly simple, but I have recently discovered BOINC, a client that interfaces with a number of different organizations in a standardized way. With the help of BOINC I have joined Primenet, which searches for large (non-Mersenne) prime numbers, as well as LHC@home, which analyzes data from/for the LHC.

    As a side note, I’d like to point out that it must suck to be the owner of the computer that found the second prime: if it had been found just a few days earlier then he would have won the $50,000 prize from the EFF. Oh well, I guess it can’t be that bad–having your name go down in history as one of the discoverers of one of the largest primes. Now the race is on for the first 100 million digit prime.

  2. That is really a superhuman achievement. The shear processing power behind such large numbers must be a truly amazing to work with. I’m glad that there are people out there using immense amounts of RAM to fight mankind’s battles of discovery.

  3. wow I never knew prime numbers were so important. Especially, enough for you to will $100,000. I would hate to see a prime number on a math test with more than 1,000,000,000 digits in it.

  4. I vaguely rememeber my Dad running program trying to find a large prime number. I wonder if this is what he was trying to do. I would have thought it would be easy to find a large prime number using a program but i guess not since they would give $100,000 to find one.

  5. This is very interesting indeed. I may have to try outsourcing my computer in order to win $100k. I wonder what applications prime numbers are used for outside of encryption?

  6. The idea of opening this software for anyone to have a stab at finding these numbers is very interesting. I remember reading, I think in Popular Mechanics, that the playstation 3 consoles, which can connect to the internet via wifi, have been used remotely to compute something having to do with protein folding. I think that OU has also linked all of their computer lab computers together to do immense computations while not actively used by a student. I don’t know for sure what the drawbacks are to using a network of computers versus one very powerful computer are, but it seems like these principles could be used to compute even larger primes. Perhaps that is what Prof Tao did at UCLA?

  7. First, I am greatly amused that my internet almost crashed when I tried to load the largest known prime number. Secondly, why is our discrete math class learning about discrete math when we could be trying to win $250,000?

  8. I can’t even begin to conceive how big a number with 12,978,189 digits would be. Just think, one trillion has only 12 digits… This is like comparing the size of a human to the sun. It’s amazing to think how far we’ve come with technology. To be able to accurately come up with numbers this big is astounding. Let alone, prime numbers. It’ll be interesting to see where the next 20 years will take us.

  9. Pingback: Prime Numbers: The “How many are there?” Edition « OU Math Club

  10. Hi,

    I’m a contributor to the GIMPS project and I’ve made the official verification of the last 7 Mersenne primes found by the GIMPS project.

    I’m looking for Math help about a conjecture we have about a primality test for Wagstaff numbers ( (2^q+1)/3 ).
    Sir Wagstaff has asked a student to search for such a proof, but AFAIK he found nothing yet.

    In few words, it is well known that the method (LLT = Lucas-Lehmer Test) used for proving that a Mersenne number is prime can also be used for Fermat numbers. There is also a LLR (Lucas Lehmer Riesel test) for numbers of the form: k*2^n +/- 1 .

    However, we think that a modified version of the LLT “could” be used (once proven) for proving that a Wagstaff number is prime.
    Up to now, we only have a sufficiency proof, providing a PRP test. We are looking for the necessity proof.

    This work is based on the properties of a DiGraph under x^2-2 modulo a prime, using the Cycles rather than the Tree.

    Why this is important ? Because that would be the first fast primality test for a kind of numbers that are not of the N-1 or N+1 form, like Mersenne and Fermat numbers are.

    Look at: http://tony.reix.free.fr/Mersenne/SummaryOfThe3Conjectures.pdf
    and: http://trex58.wordpress.com/math2matiques/ .

    Regards,
    Tony Reix

    • Tony,

      Thanks for the comment! We’ll be sure to pass along your invitation to the number theorists in the department. Please keep us updated on your investigations!

  11. Hi,
    Thanks for passing my invitation to OU number theorists.

    I’m an amateur. So my skills are limited to some basic methods that Lehmer, HC. Williams, and P. Ribenboim used in their books. There are many other ways to prove the theorem (the LLT) that is used for searching for Mersenne primes. I hope that someone will be interested and will use his Math skills to make progress in this area, exploring the cycles of the DiGraph under x^2-2. Anton Vrba and Robert Gerbicz used different technics than mine.

    What I found surprising and so beautiful with the Lucas-Lehmer Test is that it is so… simple : start with S=4, compute S^2-2 (modulo a 2^q-2 Mersenne number to be checked), and do it again, till q-2. If it is 0, then the number is prime. Astonishly simple ! (though it requires very fast FFT and computers to do it). These times, I’m using a 2xquad-Nehalem machine for testing some Mersenne numbers with the exponent of size 46M. It takes only about 5.5 days per number, using the Glucas program.

    The PRP test for Wagstaff numbers has been implemented by Jean Penné, based on the GIMPS mprime library. We hope to find a big Wagstaff PRP (PRobably Prime) one of these days…

    About my investigations, I’m afraid I’ve made no progress since months. I should summarize the ideas I had… Maybe that could help. Not sure…

    For people interested with this subject, I recommend the following books: “The little book of Bigger primes” by Paulo Ribenboim, and “Édouard Lucas and primality testing” by HC Williams (who gave me some help).

    Join the GIMPS !

    Tony

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s