**The theme of That’s Maths (TM008) this week is prime numbers. Almost all the largest primes found in recent years are of a particular form **

*M*(

*n*)

*=*2

^{n}

*−*1

**. They are called Mersenne primes. The**

*Great Internet Mersenne Prime Search*(GIMPS) is aimed at finding ever more prime numbers of this form.**The search for the largest prime will never end: Euclid proved that the number of primes is unlimited. His argument is a model of logical simplicity. Suppose there are only a finite number of primes, and let ***p*** be the largest of them. Form the number ***N* = *p*!+1**. Clearly, ***N*** is not evenly divisible by any number up to ***p***, because it always leaves a remainder of **1**. So, either ***N*** is divisible by some prime number greater than ***p*** or it is itself prime. In either case, there is a prime number greater than ***p***. **

**Primes “thin out” with increasing size. The ***n-***th prime is roughly of size ***n*** log***n*** (this is the essence of the prime number theorem). Yet, occasionally we find primes close together. Indeed, it appears that there are an infinite number of prime pairs (**2*n**−*1, 2*n*+1**). This is the ‘twin prime hypothesis’, which has never been proved.**

**On the other hand, there are arbitrarily large gaps between primes. This is simply shown by construction. For any ***n***, take the sequence {***n*!+2,*n*!+3, …, *n*!+*n***}; the first number is divisible by **2**, the second by **3** and so on, so the sequence comprises ***n**−*1** consecutive composite numbers.**

**Mathematicians have long searched for functions that generate only prime values. Euler found a nice quadratic polynomial ***f*(*n*) = *n*^{2} −*n*+41** that is prime for the first **40** values of ***n***. But of course ***f*(41) =41^{2}** is composite. And it is not too difficult to show that any polynomial with integer coefficients inevitably takes composite values for some (most?) integer values of the argument ***n***.**

**This result was originally found by Christian Goldbach, a friend of Euler, who also surmised that every even number is the sum of two primes. Goldbach’s conjecture is another result crying out for a proof. Fame awaits anyone who can prove it.**