# If $n$ is the sum of two squares, then $n$ is not congruent to $3\pmod 4$

I have to prove that if $$n\in\mathbb{Z}$$ is the sum of two squares, then $$n\not\equiv3\pmod4$$.

I tried to do a proof by contradiction (showing that a contradiction arises using the form $$p\wedge\neg q$$). My proof is:

I will prove that a contradiction arises when $$n$$ is the sum of two squares & $$n\equiv3\pmod 4$$. Assume $$n=a^2+b^2$$, where $$a,b\in\mathbb{Z}$$. Then, if $$n\equiv3\pmod 4$$, by reducing modulo $$4$$, we have that $$3=a^2+b^2$$. This is not possible for the sum of any two squares. Consider the fact that $$0^2+0^2=0$$, $$0^2+1^2=1$$, $$1^2+1^2=2$$, $$1^2+2^2=5$$. Since $$5>3$$, any successive sum of squares will be greater than $$3$$. Since the sum of squares will never equal $$3$$, there arises a contradiction to the statement that $$3=a^2+b^2$$. Therefore, it must be true that if $$n$$ is the sum of two squares, then $$n\not\equiv3\pmod 4$$.

Is this proof sufficient to satisfy the original statement? I'm particularly unsure about the step "if $$n\equiv3\pmod 4$$, by reducing modulo $$4$$ we have that $$3=a^2+b^2$$".

• $1^2+2^2=5\cong 1\pmod4$. Jul 11, 2019 at 7:18
• On notation: It is best to use $=$ only for "equals". E.g. 3\equiv a^2+b^2 \mod 4, which gives $3\equiv a^2+b^2 \mod 4.$ Jul 17, 2019 at 16:42
• If $n=a^2+b^2$ and $n\equiv 3$ then $a^2+b^3 \equiv 3$ because $n$ and $a^2+b^2$ are the same thing Jul 17, 2019 at 16:50

The squares in $$\Bbb Z_4$$ are $$0$$ and $$1$$ (calculate all 4 possible squares to see this). Thus the sum of two squares is either $$0,1,2$$.
The proof is almost correct, you had the right idea. The step $$(n \equiv 3 \mod 4) \Rightarrow 3 = a^2 + b^2$$ is indeed wrong, if you review the definition of a congruence the conclusion you can derive is, $$3+4k = a^2+b^2$$ for some $$k \in \mathbb{Z}$$. This is basically just a more cumbersome notation for a congruence though, and I propose to keep doing calculations modulo 4. You should prove that any square integer, if reduced mod 4, is congruent to either 0 or 1 (this can be done by just testing all the possibilities) so the sum of two squares may never be congruent to 3 when reduced modulo 4. This concludes the proof.