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:
- Any number can be written as a product of prime numbers as stated in the fundamental theorem of arithmetic.
- 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:
- Non prime
Why? Because any natural number > 1 has to be either prime or non prime.
- 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!
- 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.