1
$\begingroup$

I'm trying to prove the following theorem:

Let $a,b\in\mathbb{Z}$ . Then $$a^{2}+b^{2}\equiv0\pmod 4 \iff a \;\text{and}\; b\;\text{are even}$$

I always struggle to prove some number is odd or even. How to prove it? I thought of using the $(a+b)^2=a^2+2ab+b^2$ formula but not sure how.

$\endgroup$
  • $\begingroup$ There're only four cases to enumerate. $\endgroup$ – Saad Apr 10 '19 at 9:41
2
$\begingroup$

If $c$ is even, then $c^2\equiv0 \pmod 4;$ if $c$ is odd, then $c^2\equiv1\pmod4$.

Therefore if $a$ and $b$ are both even,

then $a^2+b^2\equiv0\pmod4;$

if $a$ and $b$ are both odd,

then $a^2+b^2\equiv2\pmod4;$

and if one of $a$ and $b$ is even and the other is odd,

then $a^2+b^2\equiv1\pmod4.$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Hint: If $a$ or $b$ or both are odd, then $(2c+1)^2 = 4c^2+4c+1 \equiv 1 \mod 4$ and $(2c+1)^2 + (2d+1)^2= 4c^2+4c+4d^2+4d +2 \equiv 2 \mod 4$.

But if $a$ and $b$ are even, then $(2c)^2+(2d)^2 = 4c^2+4d^2\equiv 0\mod 4$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ what is $c$? why did you look at $(2c+1)^2$? Also what if only one of the numbers is odd? $\endgroup$ – vesii Apr 10 '19 at 9:52
  • $\begingroup$ @vesii: If $a$ is odd,then it can be written as $$a=2c+1$$ for some $c \in \Bbb Z$ $\endgroup$ – Chinnapparaj R Apr 10 '19 at 9:53
  • $\begingroup$ @Wuestenflux You say "if a or b or both are odd..." but only consider the case when they are both odd. $\endgroup$ – PierreCarre Apr 10 '19 at 19:21
0
$\begingroup$

$\Rightarrow$:

By the rules of modular arithmetic we have \begin{align} 0 &= (a^2 + b^2) \bmod 4 \\ &= \left( \left( a^2 \bmod 4 \right) + \left( b^2 \bmod 4 \right) \right) \bmod 4 \end{align} For each summand we have \begin{align} x^2 \bmod 4 &= \left( \left( x \bmod 4 \right) \left( x \bmod 4 \right) \right) \bmod 4 \\ &\in \{ y^2 \bmod 4 \mid y \in \{0,1,2,3\} \} = \{ 0, 1 \} \quad (*) \end{align} So for the expression $$ \left( \left( a^2 \bmod 4 \right) + \left( b^2 \bmod 4 \right) \right) \bmod 4 $$ we have the possible cases $0+0$, $0+1$, $1+0$ and $1+1$. This vanishes modulo $4$ only for the case $0+0$.

Now $x^2 \bmod 4$ only vanishes for $x \bmod 4 \in \{ 0, 2 \}$, see display $(*)$, which means $x = 4k$ or $x = 4k + 2$ for some integer $k$ and both cases can be divided by $2$, thus are even.

$\Leftarrow$:

$a = 2p$ and $b=2q$ for some integers $p, q$. Then we have \begin{align} (a^2 + b^2) \bmod 4 &= (4p^2 + 4q^2) \bmod 4 \\ &= \left( \left(4p^2 \bmod 4\right) + \left(4q^2 \bmod 4 \right)\right) \bmod 4 \\ &= (0 + 0) \bmod 4 \\ &= 0 \end{align}

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

If both $a$ and $b$ are odd numbers then $a = 2k_1+1, b=2 k_2+1$ and you have that $$ a^2+b^2 = (2k_1+1)^2+(2 k_2+1)^2 = 4k_1^2+4 k_2^2 +4k_1+4k_2+2 \equiv 2 (mod\,\, 4) $$

If one is odd (for instance $a$) and the other is even, then $a =2 k_1+1, b=2k_2$ and

$$ a^2+b^2 = (2k_1+1)^2+(2k_2)^2 = 4k_1^2+4k_2^2+4k_1+1\equiv 1 (mod\,\,4) $$

If both $a$ and $b$ are even, $a=2k_ 1, b=2k_2$ and $$ a^2+b^2 = (2k_1)^2+(2k_2)^2=4k_1^2+ 4k_2^2 \equiv 0(mod\,\,4) $$

So you see that $a^2+b^2$ can only be congruent with 0,1 or 2 (mod 4) and is congruent with 0 if and only if both $a$ and $b$ are even numbers.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

$$a^{2}+b^{2}\equiv0\pmod 4 \iff(a+b)^2-2ab\equiv 0\pmod{4}.$$ If both $a$ and $b$ are odd, then: $$\begin{align}a+b\equiv 0\pmod{2} &\Rightarrow (a+b)^2\equiv 0\pmod{4}, \text{but}\\ 2ab\equiv 0 \pmod{2} &\Rightarrow \qquad 2ab\not\equiv 0\pmod{4}\end{align}$$ If $a$ is odd and $b$ is even, then: $$\begin{align}2ab&\equiv 0 \pmod{4}, \text{but}\\ a+b\not\equiv 0\pmod{2} \Rightarrow (a+b)^2&\not\equiv 0\pmod{4}\end{align}$$ Finally, if $a$ and $b$ are even, then: $$\begin{align}a+b\equiv 0\pmod{2} \Rightarrow (a+b)^2&\equiv 0\pmod 4\\ 2ab&\equiv 0\pmod 4\end{align}$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.