### A Mersennery Quest

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) = 2n1. 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 logn (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 (2n1, 2n+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 n1 consecutive composite numbers.

Mathematicians have long searched for functions that generate only prime values. Euler found a nice quadratic polynomial f(n) = n2n+41 that is prime for the first 40 values of n. But of course f(41) =412 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.