## Monday, 13 February 2012

### Proof by Contradiction: Infinite Prime Numbers

There are many complex and obscure methods of proving that there are infinite prime numbers, but this one is certainly the easiest and it is a demonstration of how unpredictable numbers can be dealt with in an efficient manner, it is also an easy introduction to proofs by contradiction.

First, just to clarify what proof by contradiction actually means:
1.) We assume that what we are trying to prove to be false is in fact true.
2.) If we find a contradiction in our assumed hypothesis that we have assumed then it can not be true. And that means that our assumed hypothesis is false, proving what we originally wanted.

So using this as our basis we are going to assume that there is in actual fact a finite amount of prime numbers, how many there is does not matter just that at some point there are no more prime numbers. If we multiply all of these prime numbers together we will get:

2 × × ... × pn-1 × pn

Where pn is the last prime number and this number is clearly not prime as is has every single prime number as a factor. However if we add 1 to this number then any of the prime numbers that we try to divide it by will give a remainder of 1, this means that it too is prime!
p = 2 × × ... × pn-1 × p+ 1

If this number is also prime it means that our original statement about there being finite prime numbers is incorrect, therefore there are an infinite number of prime numbers!

This took literally two lines of working to prove that there are an infinite number of prime numbers, this massive, beautiful and unfathomable concept was proved so efficiently and beautifully. This is what Maths is about, how concisely you can express complicated statements. Maths is solely about explaining the world around us and where this leads us is some amazing, incomprehensible places.