# MEC Lesson 2 – Proof by contradiction

The proof we just saw of Pythagoras’ theorem is an example of a direct proof. We gave a general argument that directly showed that $a^2+b^2=c^2$ for all right-angled triangles. In this section we are going to look at a different type of proof, called a proof by contradiction. The idea is a subtle one, so think about it carefully. The general outline is as follows.

1. We want to prove a certain mathematical statement.
2. Start by assuming that the statement we want to prove is false.
3. Use that assumption to show something impossible, or contradictory.
4. Conclude that our original assumption must have been incorrect.

To see this in action we are going to think about prime numbers.

#### Prime Numbers

Prime numbers are the building blocks of whole numbers. They are the smallest parts into which we can break numbers down. For example, we can break down the number 15 as follows.

$15 = 5 \times 3$

The point is that we can’t break these numbers down any further. We call numbers like this prime. So in this example we see that 5 and 3 are prime numbers, and that 15 is not (because it could be broken down into smaller pieces). Here are some of the smallest prime numbers.

$2, 3, 5, 7, 11, 13, 17$

Think about some of the numbers that have been missed out on this list and check to see why they aren’t prime e.g. $4=2\times2$. You may have noticed that we skipped over 1. Well 1 is a bit weird because we can do silly things like write $3 = 3 \times 1 = 3 \times 1 \times 1$ and so on. For this reason we just choose to ignore 1 and say that it is not prime.

Okay so we have this idea of prime numbers, and we have seen that some numbers, like $7$, are prime, while others, like $4$ and $15$ are not. The question is, how many prime numbers are there? The periodic table is a table of elements from which all of matter is made. All of the complexity of nature is built from this list of 118 elements. So what about numbers? How many prime numbers do we need to build all the numbers in the world?

The answer is that there are infinitely many prime numbers. That is, the primes go on and on forever. If we were to extend the list above $2, 3, 5, 7, 11, 13, 17, \ldots$ it would never end. There is no last prime number. How are we going to prove something like this? The idea is, of course, to use a proof by contradiction. Let’s give it a try:

Step 1. Assume the statement is false. That is, suppose we have only finitely many prime numbers. Here they are now.

$p_1, p_2, \ldots, p_n$

We don’t know how many there are, only that the list is finite. We say there are $n$ of them where $n$ is some number we don’t know. It could be 1,456,345, perhaps it’s 73, it doesn’t matter. All that matters is that we are pretending that it is finite.

Step 2. Now we need to come up with a contradiction. Consider the following number:

$P = p_1p_2p_3\cdots p_n + 1$

That is, we just multiply all the prime numbers together and add 1. For example, if the list of all prime numbers was $2, 3, 5$ (it clearly isn’t, but just for a concrete example), then this number would be $31$. What happens if we try to divide our new number $P$ by a prime number? I claim that we will always get a remainder of 1. In our example this is plain to see – 31 divided by any of our primes 2, 3 or 5, has remainder 1. This holds for our general number $P$ too, since this is exactly how we built it!

Question: Is $P$ a prime number? Well, observe that $P$ is larger than any of the primes on our list $p_1, \ldots, p_n$, since we made $P$ by multiplying all the primes together and adding 1. So $P$ can’t be on the list, and so it cannot be prime (since we assumed the list contained all the primes!).

On the other hand, if $P$ is not a prime number, then by definition we must be able to break it down into smaller prime pieces (like we did with $15 = 5 \times 3$). So we should be able to write $P$ as a product of primes on our list.  But we just observed that no primes on our list divide $P$. If $P$ was a product of primes, then those primes must divide $P$ (just as both $5$ and $3$ divide $15$).

Step 3. So $P$ cannot be a prime, and cannot be a non-prime! But this cannot be – it must be one or the other. Therefore this is our contraction. It shows us that our original assumption must have been false!

Step 4. So our original assumption, that there were only finitely many primes, must be false. We can therefore conclude that there are indeed infinitely many primes!

Next lesson we will look at some graph theory and you will try and come up with your own idea of a mathematical theorem!