Showing posts from August 10, 2017

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: P1P2P3….Pn
Lets try to form a new number Q the following way: Q = P1x P2x P3x….Pn+ 1

Now, Q can either be: PrimeNon primeWhy? Because any natural number > 1 has to be either prime or non prime.
If its: 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,…