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

...

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.

Other facts about twin primes:

Other than (3, 5), all twin primes have the form (6n - 1, 6n + 1).

In 1919 Viggo Brun showed that the sum of the reciprocals of the twin primes converges to a definite number, now known as Brun's constant (approximately 1.902160578).

In 1994, while in the process of estimating Brun's constant by calculating the twin primes up to 10

^{14}, Thomas Nicely discovered the infamous Pentium bug.

The largest known twin primes (as of January 2010) are a pair of 100,355 digit primes with the values 65516468355 * 2

^{333333}± 1.

## No comments:

Post a Comment