Monday, January 4, 2010

Unsolved: Twin Primes Conjecture

Prime numbers, as most school children can tell you, are those numbers that are evenly divisible by only themselves and 1. The first few primes are

2, 3, 5, 7, 11, 13, 17...

We've known that there are infinitely many primes since c. 300 BC when it was proven by Euclid of Alexandria. Euclid used a very simple and elegant proof by contradiction.

Euclid's proof of the infinitude of primes

First, assume that there are a finite number of primes, p1, p2, p3, ..., pn.

Now let

Q = (p1 * p2 * ... * pn) + 1

That is, Q is equal to all of the primes multiplied together plus one.

By the Fundamental Theorem of Arithmetic, Q is either prime or it can be written as the product of two or more primes. However, none of the primes in our list evenly divides Q. If any prime in our list did evenly divide Q, then that same prime would also evenly divide 1, since

Q - (p1 * p2 * ... * pn) = 1

This contradicts the assumption that we had listed all the primes. So no matter how many primes we start with in our list, there must always be more primes. (Note that this proof does not claim that Q itself is prime, just that there must be some prime not in the initial list.)

Twin primes

Twin primes are those pairs of numers that have a difference of two, and that are both prime.

3, 5
5, 7
11, 13
17, 19
...

The Twin prime conjecture, which dates back to the 18th century, simply states that there are infinitely many twin primes.

Given the simplicity of Euclid's proof of the infinitude of primes, it's tempting to hope for an equally simple proof to the Twin prime conjecture. Needless to say, such a proof has not been found.