Proof that if $p\equiv3\,\left(\mbox{mod 4}\right)$ then $p$ can't be written as a sum of two squares

I'd appreciate your help showing that if $p\equiv3\,\left(\mbox{mod 4}\right)$ then p can't be written as a sum of two squares.

Thanks!

-

Any square of an integer must be equivalent to 0 or 1 $\pmod{4}$, so if you add two of them, you can't get something which is equivalent to $3 \pmod{4}$.

-
Thanks for the help John. And also thanks to the other repliers. I love math.stackexchange... –  Serpahimz Jan 16 '13 at 23:21

Every number is congruent to $0$, $1$, $2$ or $3$ or modulo $4$.

Notice that $0^2 \equiv 0 \bmod 4$, $1^2 \equiv 1 \bmod 4$, $2^2 = 4 \equiv 0 \bmod 4$ and $3^2 = 9 \equiv 1 \bmod 4$. Thus, all square numbers are congruent to either $0$ or $1$ modulo $4$.

Assume that $n$ is the sum of two square numbers, then it is congruent to $0+0 = 0$, $1+0 = 1$, $0+1 = 1$ or $1+1 = 2$ modulo $4$. The contrapositive tells us that if $n$ is not congruent to either $0$, $1$ or $2$ modulo $4$ then it is not the sum of two square numbers. This proves your statement.

-

Hint: Take any integer number. If even, its square is divisible by four. If odd, its square gives remainder 1 when divided by 4.

-