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: P 1 P 2 P 3 ….P n Lets try to form a new number Q the following way: Q = P 1 x P 2 x P 3 x ….P n + 1 Now, Q can either be: Prime Non prime Why? 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 mor