A Mersenne number is a number that is one less than a power of 2. For example, 2, 4, 8, 16, 32 and 64 are all powers of 2, so 1, 3, 7, 15, 31 and 63 are the first six Mersenne numbers. To form the 7th Mersenne number, take seven twos, multiply them together and subtract one. This gives you 127. Mathematicians write this as M₇ = 2⁷ - 1 = 127.

Interestingly, if you write a Mersenne number in the binary system (base two), it comes out as a whole load of ones: M₇ = 1111111.

Prime Numbers

The study of Mersenne numbers is part of the study of prime numbers. Most numbers can be divided evenly by others. For example, 12 can be divided by 2, 3, 4 or 6, while 493 can be divided evenly by 17 or 29. This can be represented graphically by arranging the number as dots in a rectangular array. The number 12 can be arranged as:

Some numbers can't be divided evenly in this way. If you have 17 dots, for example, they can not be arranged in a neat rectangle, other than the following:

That is, 17 = 17 x 1. Big deal!

A number that can't be divided evenly by any other number (except 1) is called a prime number. They are considered to be the building blocks of numbers, because every number is either a prime or can be made by multiplying primes together in one and only one way. Numbers greater than 1 that are not prime are called composite numbers, because they are composed by multiplying primes together. The first few primes are 2, 3, 5, 7, 11, 13 and 17. Primes are quite common but get rarer as you start looking at bigger and bigger numbers.

For small numbers it is easy enough to check if the number is prime. For the number 101, for example, we just divide it by all the numbers less than it. If none of them go into it evenly, then it is prime. This test can be made more efficient by testing for divisibility by 2, then dividing by only the odd numbers. It can be made even more efficient by noting that if the number is composite (not prime), then it must be made up of two numbers multiplied together. One of these must be smaller than and the other bigger than the square root of the number. So we need only test by dividing by those odd numbers up as far as the square root. As the square root of 101 is 10.05, we only need to divide by 3,5,7 and 9. As none of these go into 101 evenly, it is prime.

For bigger numbers it is not so easy to check if they are prime. The number 2,147,483,648 for example has a square root of 46,340.95. To divide this number by all the odd numbers up to 46,339 would take a lot of effort and was never considered worth the trouble. In the days before computers, ten-digit numbers were too big for people to know whether they were prime or not. Even with today's fast computers it would still take an inordinate amount of time to check really large numbers by the division method mentioned here.

Who was Mersenne?

Marin Mersenne (1588 - 1648) was a French monk, philosopher and mathematician of the 17th Century. He was friendly with many other philosophers of the day, including Fermat, Pascal and Galileo. As there were no scientific or mathematical journals, mathematicians had no way of communicating their results to each other. Mersenne acted as a sort of clearing house for mathematical ideas. People would send him details of their discoveries and he would pass them on. Mersenne himself made many discoveries, including the use of a pendulum as a regulator in clocks. It is not for these that he is now famous, but for the numbers named after him.

A Formula for Prime Numbers

It has been known since the time of Euclid (5th Century BC) that there are an infinite number of primes. It is quite easy to prove, and Euclid's proof is a wonderful example of 'proof by contradiction', also known as 'reduction to absurdity'. The mathematicians of the 17th Century searched for a formula that would produce prime numbers. For example, the formula x² + x + 41 gives a series of prime numbers when you put in different values of x. If formulae are all Greek to you, this can be presented in the form of a sequence of instructions:

• Pick a small number, such as 2, 5 or 17
• Multiply it by itself
• Add the original number
• Add 41.

Hey presto! You now have a prime number. Unfortunately, this process only works if the first number you pick is less than 40. Mersenne, Fermat and friends tried to find a formula that would always produce a prime number. Such efforts appear to be doomed to failure - nobody has ever succeeded in finding one.

Mersenne Primes

Mersenne started looking at the numbers 2ⁿ - 1, which were later named Mersenne numbers after him. This entry will use the shorthand notation M_n for such a number. Mersenne wanted to know if any such numbers were prime. A Mersenne number that is prime is known as a Mersenne prime.

He quickly found that if n is not a prime, then M_n is not a prime. In fact this is easy to see if you write the number in binary as suggested earlier on. For example, M₆ when written in binary is 111111, a string of six ones. But since 6 = 2 x 3, we can group this into groups of 3 ones: 111,111. It is now easy to see that this is divisible by 111 (still in binary), because it equals 111 x 001,001. Similarly, M₁₀ can be written as a string of ten ones but as 10 = 2 x 5, this can be written 11,11,11,11,11 which is clearly divisible by 11. So the conclusion is that when n is not prime, M_n is also not prime and is of no further interest.

So now we consider the case where n is prime. We use the letter p instead to show we are talking about prime numbers. If p is prime, is M_p prime as well? Look at the following table:

This would be wonderful except for that 'No!' in the middle. M₁₁ = 2047 = 23 x 89 so we have not got a formula for prime numbers.

Nevertheless, Mersenne decided to continue looking to see what other Mersenne numbers were primes. He speculated that for numbers bigger than M₁₉ up as far as M₂₅₇, only the following Mersenne numbers are prime: M₃₁, M₆₇, M₁₂₇ and M₂₅₇. Why exactly he picked these numbers is not clear. Even the smallest of these, M₃₁, is an enormous number, with ten digits. The largest, M₂₅₇, has 78 digits. It was beyond the abilities of Mersenne or anybody else at the time to prove his assertion.

Mersenne Proved Wrong

In 1750, many years after Mersenne died, the great Leonhard Euler proved that the first of Mersenne's numbers, M₃₁, is in fact prime and that Mersenne was right so far. He used methods devised by himself and Fermat, along with a lot of hard work.

The first inkling that Mersenne was wrong was in 1876, when Edouard Lucas (1842 - 1891) devised a simple test for checking the 'primeness' of Mersenne numbers. With it he managed to show that M₆₇, claimed to be prime by Mersenne, was in fact not so. But his method gave no indication of what numbers would divide into it.

Lucas's method was later refined by Derrick H Lehmer (1905 - 1991) into a form so simple that it is given here in only four lines:

• Set U = 4
• Repeat the next line (p - 2) times:
• Set U = (U² - 2) modulo M_p
• If U = 0 at the end of this procedure, then M_p is prime, otherwise it is composite.

The third line of this is the only one that might seem in any way mysterious. What it means is: take U, multiply it by itself, subtract 2, then get the remainder after dividing by M_p. Store the result back into U.

Subsequent searching showed that Mersenne had missed a few primes: M₆₁, M₈₉ and M₁₀₇. He was also wrong about M₂₅₇, which is not prime. Thus, Mersenne was wrong as often as he was right. Nevertheless, his audacious claim spurred many a mathematician to push the limits of mathematics to try to prove him right or wrong.

The Role of Cole

Although Lucas had shown that M₆₇ was not a prime, it was still not known what the factors (numbers that divide evenly into it) were. In 1903, a mathematician by the name of Frank Nelson Cole (1861 - 1926) gave a 'lecture' to the American Mathematical Society entitled 'On the Factorisation of Large Numbers'. Without saying a word, Cole proceeded to write on a blackboard the calculations for 2 to the power of 67, then carefully subtracted 1. This was M₆₇ and it is equal to 147,573,952,589,676,412,927. He then wrote out 193,707,721 x 761,838,257,287 on the other side of the board and proceeded to work out the multiplication by hand. The final product was written at the bottom and was seen to be identical to M₆₇. Cole, without saying a word, had just shown in terms everyone could understand that Mersenne was wrong. He received a standing ovation. Afterwards he admitted that it had taken him 'three years of Sundays' to find the result.

The Era of the Computer

One final section in the story of the Mersenne primes began in 1952, when Raphael Robinson (1911 - 1995) managed to find five more Mersenne primes on a new-fangled electronic computer. The simplicity of the Lucas/Lehmer test given above makes it ideal for performing on a computer, but you need a fast one. As computers got faster, the production of new Mersenne primes was seen as a good demonstration of the powers of the new computers, so a computerised hunt has taken place since then - every few years a new Mersenne prime is discovered. It is estimated that each new Mersenne prime takes more computation to discover than all the previous ones put together.

You can get an up-to-date list of all known Mersenne primes, and you can also join in the search at the Great Internet Mersenne Prime Search site. This gives you free software and all the information you need to know if you want to help in the search. So far they have found six!

A New Lease of Life for Prime Numbers

Prime numbers were for a long time considered to be one branch of mathematics that would never find any application in the real world. They were pure mathematics, knowledge for its own sake. Two discoveries in the last 30 years or so have changed this image. One is amusing, the other important in the business world.

Periodic cicadas - a type of insect found in North America - hibernate for many years, lying dormant in the ground. After a long period, they emerge to begin a new life. It has been found that there are two distinct types of Cicada, those that remain dormant for 13 years and those that choose to sleep for 17 years. It is no coincidence that these two numbers are primes! This is explained in the Guide entry on cicadas.

The RSA Public Key encryption system is a wonderful method of sending information in an encrypted form so that nobody can intercept and read the sensitive information. It allows the key for encrypting the information to be published for everyone to read, because it uses a different key for decryption, one that is known only to the receiver of the message. This system is based very heavily on prime numbers.

While neither of these two examples relates specifically to Mersenne numbers, it does show that mathematics has a way of appearing where you least expect it. The study of prime numbers, kept alive in the 17th Century by Mersenne, has become an important part of today's world and our understanding of it.