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.

Popular posts from this blog

Dynamic Programming Example

SAP Labs India Interview Experience