 ### Patrick Stevens

Former mathematics student at the University of Cambridge; now a software engineer.

Here I explain proof by contradiction so that anyone who has ever done a sudoku and seen algebra may understand it.

Imagine you are doing a sudoku, and you have narrowed a particular cell down to being either a 1 or a 3. You’re not sure which it is, so you do the “guess and see” approach: you guess it’s a 1. That forces this other cell to be an 8, this one to be a 5, and then - oh no! That one over there has to be a 7, but there’s already a 7 in its row! That means we have to backtrack: our first guess of 1 was wrong, so it has to be a 3 after all.

That was a proof by contradiction that the cell was a 3.

Now I present the standard proof that $\sqrt{2}$ is not expressible as a fraction $\frac{p}{q}$ where $p, q$ are whole numbers.

Analogy: “the cell was a 1” corresponds to “$\sqrt{2}$ is fraction-expressible”. “The cell was a 3” corresponds to “$\sqrt{2}$ is not fraction-expressible”.

Suppose $\sqrt{2}$ were fraction-expressible. Then we could write it explicitly as $\sqrt{2} = \frac{p}{q}$, and we can insist that $q > 0$: if it’s negative, we can move the negative up to the $p$. If we clear denominators, we get $q \sqrt{2} = p$; then square both sides, to get $2 q^2 = p^2$.

But now think about how many times 2 divides the left-hand side and the right-hand side. 2 divides a square an even number of times, if it divides it at all (because any square which is divisible by 2 is also divisible by 4, so we can pair off the 2-factors). So 2 must divide $q^2$ an even number of times, and hence the left-hand side an odd number of times (because that’s $2 \times q^2$). It divides the right-hand side an even number of times. So the number of times 2 divides $p^2$ is both odd and even. No number is both odd and even!

We’ve done the equivalent of finding a 7 appearing twice in a single row. We have to backtrack and conclude that the starting cell was a 3 after all: $\sqrt{2}$ is not fraction-expressible.