2
$\begingroup$

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$".

$\endgroup$
3
  • $\begingroup$ $1^2+2^2=5\cong 1\pmod4$. $\endgroup$
    – Berci
    Jul 11, 2019 at 7:18
  • $\begingroup$ 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.$ $\endgroup$ Jul 17, 2019 at 16:42
  • $\begingroup$ 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 $\endgroup$ Jul 17, 2019 at 16:50

2 Answers 2

6
$\begingroup$

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$.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .