## Nasty Squares

May 12, 2009 09:43 by scibuff

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

$n^{2} + (n+1)^{2} + (n+2)^{2} = m^{2}\ (1)$

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 $0 = 1$.

Proof: First, let’s make our lives a bit easier by renaming the terms. If there are integers $n,m\varepsilon Z$ satisfying the equality in $(1)$, then taking $n=n+1$ we can rename the terms to

$(n-1)^{2} + n^{2} + (n+1)^{2} = m^{2}\ (2)$

Let’s assume that there are $n,m\varepsilon Z$such that $(2)$ holds. Expanding the terms in brackets gives

$(n-1)^{2} + n^{2} + (n+1)^{2} = (n^{2} - 2n + 1) + n^{2} + (n^{2} + 2n + 1) = 3n^{2} + 2 = m^{2}$

Now look at $3n^{2} + 2$ and apply arithmetic modulo 3. Clearly

$3n^{2}\equiv 0\ mod\ 3$,

and so

$3n^{2} + 2\equiv 0 + 2\equiv 2\ mod\ 3$.

Since

$3n^{2} + 2 = m^{2}$

it follows that

$m^{2}\equiv 2\ mod\ 3\ (3)$

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 $n\varepsilon Z$ such that $n\equiv 0\ mod\ 3$. Then

$n^{2}=n\times n\equiv 0\times0\equiv0\ mod \ 3$

Similarly, if $n\equiv 1\ mod\ 3$, then

$n^{2}=n\times n\equiv 1\times1\equiv1\ mod \ 3$

and finally, if $n\equiv 2\ mod\ 3$, then

$n^{2}=n\times n\equiv 2\times2\equiv4\equiv1\ mod \ 3$

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

there is no $m\varepsilon Z$ such that $m^{2}\equiv 2\ mod\ 3\ (4)$

But that is exactly the opposite result of what we concluded in $(3)$. Clearly, $(4)$ is correct, therefore $(3)$ must be false. We arrived at the result in $(3)$ by assuming that there are integers $n,m\varepsilon Z$ such that

$(n-1)^{2} + n^{2} + (n+1)^{2} = m^{2}\$

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

$(n-1)^{2} + n^{2} + (n+1)^{2} = m^{2}\$, or equivalently

$n^{2} + (n+1)^{2} + (n+2)^{2} = m^{2}$

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