### 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,…

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,…