Proof by contradiction

Why examples are not enough

Look at the numbers $n^2 + n + 41$ for $n = 0, 1, 2, 3, \ldots$

• $n = 0$ gives $41$, a prime.
• $n = 1$ gives $43$, a prime.
• $n = 2$ gives $47$, a prime.
• $n = 3$ gives $53$, a prime.

They stay prime all the way up to $n = 39$. It is tempting to say that they are always prime. But $n = 40$ gives $40^2 + 40 + 41 = 1681 = 41 \times 41$, which is not a prime.

Forty good examples proved nothing. A proof is a chain of correct steps that shows a statement is true in every case, even in the cases that nobody has checked. On the other hand, one example that fails, a counterexample, is enough to show that a statement is false.

The idea of a proof by contradiction

Sometimes the easiest way to prove a statement is to show that it cannot be false.

1. Suppose the opposite. Assume that the statement is false.
2. Reason correctly. Use only true facts and correct steps.
3. Reach something impossible. For example, a number that is both even and odd.
4. Conclude. The supposition was wrong, so the statement is true.

You already reason like this. Asha's bag was in the classroom at 10 o'clock. Ravi says that he took it home at 9 o'clock. If his story were true, the bag could not be in the classroom at 10. It was there, so his story is false.

A first example

Statement. If $n^2$ is even, then $n$ is even.

Proof. Suppose the opposite: $n^2$ is even, but $n$ is odd. An odd number can be written as $n = 2k + 1$, where $k$ is a whole number. Then

That is two times a whole number, plus $1$. So $n^2$ is odd. But we started with $n^2$ even, and no number is both even and odd. The supposition is false, so $n$ is even.

A key fact about primes

In the course Primes, HCF and LCM you met the Fundamental Theorem of Arithmetic. Every whole number above $1$ is a product of primes in exactly one way, apart from the order. It gives us the fact that the next lesson needs.

Theorem. Let $p$ be a prime. If $p$ divides $a^2$, then $p$ divides $a$.

Why. Write $a$ as a product of primes, $a = p_1 \times p_2 \times \cdots \times p_n$. Then

So the primes of $a^2$ are exactly the primes of $a$, each one twice. If the prime $p$ divides $a^2$, it is one of these primes, because the factorisation is unique. So $p$ is one of $p_1, p_2, \ldots, p_n$, and $p$ divides $a$.

For example, $30 = 2 \times 3 \times 5$ and $30^2 = 900 = 2^2 \times 3^2 \times 5^2$. The primes that divide $900$ are $2$, $3$ and $5$, the same as for $30$.

The prime matters. $4$ divides $6^2 = 36$, but $4$ does not divide $6$. The theorem is true for primes only.

Practise with new numbers

Try it in Python

The program does two things. First it looks for the first $n$ that breaks the pattern of $n^2 + n + 41$. Then it tests the key fact for six primes and every $a$ up to $500$.

Testing $3000$ cases is a good check, but it is still not a proof. The proof is the argument with the prime factors above.

Common mistakes

• Trusting examples. Many examples that work are not a proof. One example that fails shows that a statement is false.
• Supposing the wrong thing. To prove that $n$ is even, suppose that $n$ is odd, not that $n$ is even.
• Using the key fact for a number that is not a prime. $4$ divides $36$, but not $6$.
• Stopping too early. The proof is finished only when two facts clash.

Remember these

• A proof shows that a statement is true in every case. One counterexample shows that it is false.
• Proof by contradiction: suppose the opposite, reason correctly, reach something impossible.
• If a prime $p$ divides $a^2$, then $p$ divides $a$. This follows from the unique prime factorisation.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Meena checks $n^2 - n + 41$ for $n = 1$ to $20$ and finds only primes. Has she proved that it is always prime?

2. You want to prove that $\sqrt{3}$ is not a fraction, by contradiction. What do you suppose first?

3. Explain in one sentence why the primes of $a^2$ are the same as the primes of $a$.

4. Write $12$ and $144$ as products of primes. Which primes divide both?

5. Prove by contradiction that there is no largest whole number.