Prime time

That most indivisible of friends

There's just something about prime numbers. They are islands in the sea of integers — pillars of chastity amongst so much promiscuous division, becoming exquisitely rare, but still infinite in number...

Um... right... but what is a prime number?

Like jewels in... No, quite enough of that. A prime number is just a number that has no factors except itself and one. That is, it is not evenly divisible except by itself and the number one.

This is most easily illustrated by example:

6 is divisible by 1, 2, 3 and itself. Not a prime.
13 is divisible only by one and itself. A prime!
64 is divisible by 1, 2, 4, 8, 16, 32, and itself. Definitely not a prime!
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, & 97 are all the primes smaller than 100. Try finding factors for them...

By a strange coincidence 173, the street number of my current flat, and 347, the street number of my previous flat are also both prime numbers. Totally accidental, I promise. I'm sometimes a little odd, but not that much...

As numbers get bigger, primes get rarer. Large primes have to 'resist' division from many more potential factors than do their lesser brethren. Despite that, primes keep popping up no matter how high up the integer food chain you go. Some really big prime numbers have been found by mathematicians over the years. The biggest prime found so far is a so-called Mersenne prime.

What's a Mersenne prime?

Marin Mersenne Glad you asked. Mersenne primes are a small sub-set of ordinary prime numbers that happen to take a special form — a Mersenne prime is an ordinary prime that can also be written as two to the power of another prime (though not all primes work), minus one.

For example, the third Mersenne prime is 2 to the power of five, minus one. Thirty-one.

2^⁵ = 32
32 - 1 = 31
31 is a prime.

They are named after a monk from the 16th century, Marin Mersenne (1588-1648), who defended Galileo and Descartes, first suggested the use of pendulums in clocks, and struggled to expose the pseudo sciences of alchemy and astrology. He discovered Mersenne primes while trying to find a formula that would represent all primes. He failed in that, but his name became attached to these rare primes in any case.

Mersenne primes have become famous because it's relatively easy to calculate whether or not a given number is a Mersenne prime (details...). As a result, the largest, most glamorous, primes found are often Mersenne primes.

The biggest prime number known to man

The 41st known Mersenne prime, and the largest prime number known to man, was found in May 2004 by the GIMPS project. It is:

2 to the power of 24,036,583 minus one, or:

299410429404157172089048926340446938257367722975418473547677348600097640221
100741026265865109912320858493344156415212635335213499669984946466002434564
247027257716956426621052611077416379956346589355834130669179364555490042058
951262711810999963071602089591146249605845552251245175040614646796742775814
169877977351895778922652339915229521619514779556831364845026895095824052712
207416118596253594344535443908358061475952581306252393965564387213568808870
109554001647102077512671720670861148470378380158230147594698428563233367938
062853437133547200496603279419358430694076277478477322725968421442213903047
497381792744687785378954139863274105174997747578653752738664908983344134408
505892942859396418378478851802939536123167178004544423712782896000307876370
...
...
7,234,973 other digits
...
...

The full prime number has 7,235,733 decimal digits. To print it out would require more characters than the complete works of Shakespeare. The number itself is far, far too big to imagine.

Help find the next record prime!

Care to be involved with the discovery of the next world shaking prime number?

For the several years now I have been donating the unused CPU time of my computers to the 'Great Internet Mersenne Prime Search' (or GIMPS...). Thanks to the untiring efforts of George Woltman, you can too. Point your web browser at www.mersenne.org, and download a program for either Linux or Windows.

The program runs on your computer all the time, but only uses CPU time that no other programs are using, a valuable resource that would otherwise go to waste! You may even win a share of US$100,000 — but the important thing is that you'll be helping add to humanity's store of knowledge, just by donating the CPU cycles that you are not even using...

All Known Mersenne primes

They are a rather rare bunch. It's interesting to note that the majority have only been found in the computer age (from the 1950s to the present)...

##	Mersenne Prime	Year Discovered	Digits in Prime
1	2²-1	unknown	1
2	2³-1	unknown	1
3	2⁵-1	unknown	2
4	2⁷-1	unknown	3
5	2¹³-1	1456	4
6	2¹⁷-1	1588	6
7	2¹⁹-1	1588	6
8	2³¹-1	1772	10
9	2⁶¹-1	1883	19
10	2⁸⁹-1	1911	27
11	2¹⁰⁷-1	1914	33
12	2¹²⁷-1	1876	39
13	2⁵²¹-1	1952	157
14	2⁶⁰⁷-1	1952	183
15	2^1,279-1	1952	386
16	2^2,203-1	1952	664
17	2^2,281-1	1952	687
18	2^3,217-1	1957	969
19	2^4,253-1	1961	1,281
20	2^4,423-1	1961	1,332
21	2^9,689-1	1963	2,917
22	2^9,941-1	1963	2,993
23	2^11,213-1	1963	3,376
24	2^19,937-1	1971	6,002
25	2^21,701-1	1978	6,533
26	2^23,209-1	1979	6,987
27	2^44,497-1	1979	13,395
28	2^86,243-1	1982	25,962
29	2^110,503-1	1988	33,265
30	2^132,049-1	1983	39,751
31	2^216,091-1	1985	65,050
32	2^756,839-1	1992	227,832
33	2^859,433-1	1994	258,716
34	2^1,257,787-1	1996	378,632
35	2^1,398,269-1	1996	420,921
36	2^2,976,221-1	1997	895,932
37	2^3,021,377-1	1998	909,526
38	2^6,972,593-1	1999	2,098,960
39^*	2^13,466,917-1	2001	4,053,946
40^*	2^20,996,011-1	2003	6,320,430
41^*	2^24,036,583-1	2004	7,235,733

^*It is not yet known if these are in fact the 39th, 40th, and 41st Mersenne primes, as some of the intermediate candidates have not been checked as yet...