The Infinite World of Primes

It is easy to define prime numbers: A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself.

A natural number greater than 1 that is not a prime is called a composite number. For example 2, 3, 5 and 7 are primes, but 4 (=2*2) and 6 (=2*3) are composite.

Prime numbers underlie a lot of work in cryptography. Internet privacy and security would be impossible without millennia of research into prime numbers.

Nevertheless even the most sophisticated mathematics still understand them quite poorly. The distribution and nature of prime numbers is insanely weird.

The fundamental theorem of arithmetic states that every integer larger than 1 can be written as a product of one or more primes in a way that is unique except for the order of the prime factors. But the same prime factor may occur multiple times. So a number can be written as a prime factorization $n=p_{1}*p_{2}*...*p_{t}$ . For example $36 = 2*2*3*3 = 2^2 * 3^2$ .

A fundamental statement in number theory is Euclid’s theorem that asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.

A first proof offered Euclid in Elements IX, 20. It is probably the oldest Book Proof. The form of argument is a reductio ad absurdum which seeks to demonstrate that a statement is true by showing that a false, untenable or absurd result follows from its denial.

So let’s look at the proof:

For any finite set { $p_{1}, ..., p_{r}$ } of primes, consider $n=p_{1}*p_{2}*...*p_{r} + 1$ . This n has a prime divisor p.
But p is not one of the $p_{i}$ : Othewise p would be a divisor of n AND of the product $p_{1}*p_{2}*...*p_{r}$ , and thus also of the difference $n - p_{1}*p_{2}*...*p_{r} = 1$ , which is impossible.
So a finite set { $p_{1}, ..., p_{r}$ } cannot be the collection of all prime numbers. QED