Euclid’s theorem: Proof of Infinitely many primes

Also known as the Euclid’s theorem, the theorem of infinitely many primes is one of the most elegant ones around. I came across it while brushing up on discrete math and had to blog about it.

Let's try to explain a proof of this theorem.

Before we begin, lets revisit the following things:

1. Any number can be written as a product of prime numbers as stated in the fundamental theorem of arithmetic.
2. The number sets
   
    

Here we go!

To prove: There are infinite prime numbers

Let’s dispute that claim for a second and assume that we know all the prime numbers.

Let’s write these as follows:

P1 P2 P3….Pn

Lets try to form a new number Q the following way:

Q = P1 x P2 x P3 x ….Pn + 1

Now, Q can either be:

1. Prime
2. Non prime

Why? Because any natural number > 1 has to be either prime or non prime.

If its:

1. Prime, our list was incomplete as there is at least one more prime number and more prime numbers can be generated in a similar way. Contradiction!
2. Non prime, we should still be able to write it in prime factorization form, i.e. Q should be a multiple of primes raised to some powers. But, as we can see, Q is not divisible by any of the primes in our list ( P1 to Pn ) as, upon division, 1 will always be left over.  This in turn means, that all of the prime factors of Q are not in the list, meaning our list is incomplete. Contradiction!

Hence, we can generalize that there are infinite many primes.