# integers

• May 1st 2009, 05:48 AM
mpryal
integers
Show that no integer u=4n+3 can be written as u = a^2 + b^2 where a,b are integers.
• May 1st 2009, 05:59 AM
Moo
Hello,
Quote:

Originally Posted by mpryal
Show that no integer u=4n+3 can be written as u = a^2 + b^2 where a,b are integers.

Fact : For any integer m, $m^2 \equiv 0 \text{ or } 1 (\bmod 4)$

Proof :
A number m can only be even or odd.
If it's even, it can be written m=2k, in which case, $m^2=4k^2 \equiv 0 (\bmod 4)$
If it's odd, it can be written $m=2k+1$, in which case, $m^2=4k^2+4k+1 \equiv 1 (\bmod 4)$

Now, is it possible that $u=a^2+b^2 \equiv 3 (\bmod 4)$ when $a^2$ and $b^2$ can only $\equiv 0 \text{ or } 1 (\bmod 4)$ ?