Proof By Contradiction

In this method of proof, we take the proposition we are trying to prove, and assume that the opposite is true. Then we follow a logical argument until we reach a conclusion which contradicts our original assumption. Then we know that the assumption was false, and so we have proved what we wanted to prove.

There are many very beautiful and elegant proofs which use this method. One of my favorites is the Proof of the Infinitude of Primes, given by Euclid. I shall try to present the proof here without using any too technical language!

Before we start, we have to talk about numbers. Everyone knows that if you start counting from the number 1 you could go on for ever without stopping. The way we describe this is that the set of counting numbers is an infinite set. There is no number of which you can say, this is the biggest one, we've now reached the end!

There are some special numbers in the set that have a peculiar property. These are called the Prime Numbers. A prime number can only be divided by itself or the number 1.
For example, 17 is only divisible by 17 or 1, whereas a number like 15 is divisible by 1, 3, 5, and 15 itself. So 17 is a prime, but 15 is not.

Now the question arises, is the set of prime numbers an infinite set? Do the prime numbers go on for ever, or is there a number to be found of which we can say, this is the largest prime number, and there are no more after this?

At first sight, you might think that there IS a largest prime, because as you count higher and higher, there are more smaller numbers that can potentially divide into the number you have reached. However, Euclid believed that they went on for ever, that there was an infinitude of primes. And he proved it, using reductio ad absurdum, proof by contradiction.

First, assume that there is a largest prime number, we give it the label p, and this number is divisible only by itself and 1.

Now we construct a (much larger) number by multiplying together all the prime numbers from 2 up to our number p. We label this number N.

Now, by definition, N is divisible by 1, 2, 3, and all the prime numbers up to and including the number p.

Now consider the number that follows the number N, we will label it (N+1). This number is certainly divisible by 1 and itself, as all numbers have that property. But it is not divisible by 2, since the previous number N is divisible by 2. Also, for the same reason, (N+1) is not divisible by 3, 4, 5, and so on all the way up to N, the number just before it.

Therefore we are forced to conclude that (N+1) is a prime number. But this contradicts our original assumption, since (N+1) is larger than p, and you remember that we assumed p to be the largest prime. Therefore our assumption must be false and hence there is no largest prime number.

Thus we have proved that the set of prime numbers is an infinite set.