Patrick Stevens bio photo

Patrick Stevens

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

Email Twitter Github Stackoverflow

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 is not expressible as a fraction where are whole numbers.

Analogy: “the cell was a 1” corresponds to “ is fraction-expressible”. “The cell was a 3” corresponds to “ is not fraction-expressible”.

Suppose were fraction-expressible. Then we could write it explicitly as , and we can insist that : if it’s negative, we can move the negative up to the . If we clear denominators, we get ; then square both sides, to get .

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 an even number of times, and hence the left-hand side an odd number of times (because that’s ). It divides the right-hand side an even number of times. So the number of times 2 divides 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: is not fraction-expressible.