3. Everything / Maths, Science & Technology / Mathematics Mersenne Numbers 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 Interestingly, if you write a Mersenne number in the binary system (base two), it comes out as a whole load of ones: M 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: **** **** ****or even: ****** ****** 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 - 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 He quickly found that if n is not a prime, then M 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
This would be wonderful except for that 'No!' in the middle. M Nevertheless, Mersenne decided to continue looking to see what other Mersenne numbers were primes. He speculated that for numbers bigger than M Mersenne Proved Wrong In 1750, many years after Mersenne died, the great Leonhard Euler proved that the first of Mersenne's numbers, M 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 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}- 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 Subsequent searching showed that Mersenne had missed a few primes: M The Role of Cole Although Lucas had shown that M 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. People have been talking about this Guide Entry. Here are the most recent Conversations: |
Please note that the BBC is not responsible for the content of any external sites listed. Most of the content on this site is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here to alert our Moderation Team. For any other comments, please start a Conversation below. | |||||||||||||||||||||||||||||||||||||||||||||