Number Theory: A Very Short Introduction

are called Mersenne numbers and, as we saw in Chapter 1, not all of them are prime. To explore which ones have this property, let’s draw up a table of the first few Mersenne numbers.

Table 2. Numbers of the form

It may seem tempting, on looking at these numbers, to speculate that is a prime number when n is prime, and that it’s composite when n is composite. It’s certainly true that

is composite when n is composite,

because if r divides n (where ), then it can be shown that must divide , and so is composite: for example, when and , we have

But it isn’t always true that is prime when n is prime: for example,

Mersenne studied these numbers in 1644, and claimed that is prime for each of the values

The fact that is prime was first confirmed by Euler in 1750, and in 1876 the French mathematician Edouard Lucas showed that the following 39-digit Mersenne number is also prime:

So Mersenne was correct when and . But he was wrong in the cases and , both of which give composite numbers: for example,

He omitted the cases , , and , which also give rise to primes, but when we consider the large numbers involved, he may surely be forgiven. A method for testing whether a given Mersenne number is prime is given in the next chapter.

There’s an amusing story about the number . For many years mathematicians had struggled to determine whether this number is prime, as Mersenne had claimed, and in 1875 Lucas showed that it was composite but couldn’t find its factors. It was Frank Nelson Cole, a professor at Columbia University in New York, who found them after three years of systematic searching on Sunday afternoons. He presented his results on 31 October 1903 at a meeting of the American Mathematical Society, when he quietly walked into the lecture room and in complete silence painstakingly calculated 2⁶⁷ and subtracted 1 on one side of the blackboard. He then walked over to the other side of the board and, again in complete silence, calmly multiplied the numbers 193,707,721 and 761,838,257,287, obtaining the same answer, and quietly returned to his seat. The audience erupted and gave him a standing ovation and vigorous applause. At no stage had he uttered a single word!

Why are Mersenne primes important? In the continuing search for new and larger prime numbers it’s been usual to turn to Mersenne numbers, because all recently discovered large primes have been of this form—there’s even been a postage stamp celebrating the discovery of one of them (see Figure 19). Indeed, in recent years a new international collaborative online project has developed to track down such numbers. Involving thousands of mathematicians and computer enthusiasts, it’s called GIMPS (the Great Internet Mersenne Prime Search), and since it started around 1996 it has found seventeen of them. It’s not known whether there are infinitely many Mersenne primes.

19. A postage stamp celebrates the discovery in 2001 of the 39th Mersenne prime.

At the time of writing, fifty-one Mersenne primes have been found. The most recent of these, the largest prime number currently known, was found in December 2018. It is , has almost 25 million digits, and to print it out in full at 75 digits per line and 50 lines per page would take many thousands of pages!Perfect numbers

Another important feature of Mersenne primes is their connection with perfect numbers. We recall from Chapter 1 that a number N is perfect if N is the sum of its proper factors (those that are less than N). For example, you’ve seen that

and that the next two perfect numbers are 496 and 8128. There are then no more of them until 33,550,336.

Is there a formula for perfect numbers? To find out, let’s factorize the ones we already know:

These numbers all have the form , where the number in parentheses is a Mersenne prime.

In Book IX of his Elements, Euclid investigated perfect numbers and found that the number

is indeed perfect whenever is a prime. To see why, let . Then the proper factors of are

What’s the sum of all these factors? Using the fact that

we can write

So we find, after some calculation, that the sum of all the proper factors is

which equals N.

So is perfect.

Are all perfect numbers of this type, or might there be some others? In 1638 the French philosopher René Descartes wrote to Mersenne saying that he believed that all even perfect numbers must indeed be of Euclid’s form, , for some number n, and this was subsequently proved by Euler and published posthumously. Euler also proved that every even perfect number must end with either 6 or 8: for example, the next three perfect numbers are

But what about odd perfect numbers? Descartes conjectured that these cannot exist, and it remains unknown to this day whether he was correct. But if there were any odd perfect numbers, then they would certainly be difficult to find. For a start, it’s known that any odd perfect number must be at least 10¹⁵⁰⁰, that it must have at least 101 prime factors with at least ten different ones, and that it must have the form , or , for some integer n. Few mathematicians consider their existence likely.Fermat primes

Having just looked at prime numbers of the form , let’s now turn our attention to numbers of the form . As