If $a$ and $b$ are odd then $a^2+b^2$ is not a perfect square 
Prove if $a$ and $b$ are odd then $a^2+b^2$ is not a perfect square. 

We have been learning proof by contradiction and were told to use the Euclidean Algorithm.
I have tried it both as written and by contradiction and can't seem to get anywhere.
 A: All squares are congruent to 1 or 0 mod 4. If they are odd they are congruent to 1 mod 4. therefore the sum of two odd squares is congruent to 2 mod 4. Thus not a square.
A: Here is a different way of doing this.
Suppose $a^2+b^2=c^2$ with $a$ and $b$ odd, then $c^2$ is even, so must be divisible by $4$.
Now consider the even square $(a+b)^2=c^2+2ab$. The first two terms are divisible by $4$ while $2ab$ is twice an odd number, so the equation can't hold.

One can also go to $(a+b+c)(a+b-c)=2ab$ with both factors on the left being even, but the right-hand side not divisible by $4$.

Note also that $(2m+1)^2=8\left(\dfrac {m(m+1)}{2}\right)+1\equiv 1 \bmod 8$, and though working modulo $4$ is enough here, this stronger fact is useful to know.
A: Let $a=2m+1$ and $b=2n+1$. 
Assume $a^2+b^2=k^2$. Then:
$$(2m+1)^2+(2n+1)^2=k^2 \iff \\
4(m^2+m+n^2+n)+2=k^2 \iff \\
4(m^2+m+n^2+n)+2=(2r)^2 \iff \\
2(m^2+m+n^2+n)+1=2r^2 \iff \\
2s+1=2r^2,$$
which is a contradiction. Hence, the assumption $a^2+b^2=k^2$ is false. 
