## Prime Numbers

Recently I read The Music of the Primes by Marcus du Sautoy. A prime number is "a whole number greater than one, which can only be divided into whole numbers only by itself and one."

The nice thing about the prime numbers is that it's easy to understand what they are, and you can follow some of the simple theorems like the infinity of the primes:

- Firstly suppose that there are only a finite number of prime numbers.
- Imagine making a list of all these prime numbers, finishing with the largest prime number is P.
- Now consider a new number, N, which is the product of all the prime numbers on your list up to P, plus one.
- If you divide N by
*any*of the prime numbers up to P you get a remainder of 1. So either N is prime, or there is prime number which has been missed of the list. - The assumption of a finite number of primes has led to a contradiction, therefore there must be an infinity of prime numbers.

This proof of the infinity of the primes was first written down by Euclid in roughly 300 BC. Euclid's other great contribution to the prime numbers is called the fundamental theorem of arithmetic, which states "any whole number greater than one can be written as a *unique* product of prime numbers." So for example 6936 = 2³ x 3 x 17², and this is the only prime factorisation of 6936.

Despite their apparent simplicity the prime numbers are really very hard to get a handle on. It's almost as if they appear randomly in the number line. But how can they be random, given that everything about them is defined?

The statistical distribution of the prime number is captured by the prime number theorem, which states "the number of primes between 1 and N is roughly N/ln(N)". Other ways of saying basically the same thing are "the average gap between consecutive prime numbers is roughly ln(N)" or "the chance of a number being prime is roughly 1/ln(N)". The proof of this theorem is however not simple.

Another nice limit on the prime number is the Bertrand-Chebyshev theorem which states "there is at least one prime number between N and 2N."

There are many statements about the primes which have not been proved. Particularly famous ones are the Goldbach Conjecture (1742) which states, "every whole number greater than 2 can be written as the sum of two prime numbers." This has been verified for all numbers up to 12 x 10^{17}. Another is the twin prime conjecture "there are infinitely many primes p such that p + 2 is also prime", the evidence for which is also very strong.

The daddy of unsolved prime problems is however the Riemann Hypothesis, which says "all non-trivial zeros of the Riemann zeta function have real part 1/2". The Riemann Hypothesis is in fact the central theme of du Sautoy's book, which explains in an understandable way what this means, and how it is connected to the prime numbers.