SciBuff.com

I talked about looking through some math questions on Yahoo Answers and posting solutions that are either elegant or interesting. So without too much ado, here’s the first one of the series:

Problem: Prove that there are no integer solutions to

Like so many problems in mathematics, this one is quite easy to solve if you know which tools to throw at it. Otherwise, one can always look at first few n’s, i.e. 1, 2, 3, 4, etc. and see if there is a pattern or anything that could be used in the proof.

When it comes to non-existence proofs involving perfect squares the obvious choice of “tools” is modular arithmetic. In this particular proof, I will also use proof by contradiction.

Proof by contradiction is a form of argument in which the original result is proven by disproving the opposite (formally known as the “negation” of the original statement). Basically, I will assume that there are two integers such that the equality above holds and use my “tools” to arrive at an obvious contradiction, such as .

Proof: First, let’s make our lives a bit easier by renaming the terms. If there are integers satisfying the equality in , then taking we can rename the terms to

Let’s assume that there are such that holds. Expanding the terms in brackets gives

Now look at and apply arithmetic modulo 3. Clearly

,

and so

.

Since

it follows that

This proof could be accomplished using modular arithmetic modulo 8 or 16 but the nice thing about modulo 3 is that there are only three possible remainders, namely 0, 1 and 2, in modulo 3 arithmetics (as opposed to 8 in modulo 8 and 16 in modulo 16 – you see the pattern there, right?!). Each remainder is associated with a congruence class – the set of all numbers that have the same remainder modulo 3, e.g. {1, 4, 7, 10, etc.}

We know that any integer belongs to one of the three congruence classes in modular arithmetic modulo 3. Now let us examine squares of integers and see to which congruence classes can those be assigned.

Consider such that . Then

Similarly, if , then

and finally, if , then

Thus, we can conclude that squares of all integers belong to either the congruence class or modulo 3. In particular, there is no integer whose square belongs to the congruence class modulo 3. In other words,

there is no such that

But that is exactly the opposite result of what we concluded in . Clearly, is correct, therefore must be false. We arrived at the result in by assuming that there are integers such that

Therefore, this assumption must be erronous, and the opposite must be true. Hence there are no integers such that

, or equivalently

Thus out proof is complete and we can finish it off in style by writing from latin Quod Erat Demonstrandum, which literally means “which was to be demonstrated”.