# How to prove that $441 \mid a^2 + b^2$

How to prove that $441 \mid a^2 + b^2$ if it is known that $21 \mid a^2 + b^2$.
I've tried to present $441$ as $21 \cdot 21$, but it is not sufficient.

• ? $a^2+b^2/441$ is an expression, not a statement – Hagen von Eitzen Oct 11 '17 at 9:09
• @MichaelRozenberg, are you sure that's the question? I think it was meant to be the other way around – AnotherJohnDoe Oct 11 '17 at 9:32
• – Will Jagy Oct 11 '17 at 16:43
• Why you have not accepted any of the answers below ? If you are not satisfied, please comment on them. – Mauro ALLEGRANZA Nov 13 '17 at 15:21

If $a^2+b^2$ is divisible by $3$ then $a$ and $b$ are divisible by $3$ because $$x^2\equiv0,1\pmod3.$$ Let $A=\{0,1\}$.

Thus, $3\not\in A+A$ and $0\in A+A$ for $0=0+0$ only.

Similarly,

if $a^2+b^2$ is divisible by $7$ then $a$ and $b$ are divisible by $7$ because $$x^2\equiv0,1,2,4\pmod7.$$

Lemma. If a prime $p \equiv 3\pmod{4}$ and $p$ divides $a^2+b^2$ then $p$ divides $a,b$.

Proof. Assume the contrary that $p \nmid a,p \nmid b$.

By Fermat's little theorem, we have $a^{p-1} \equiv 1 \pmod{p}, b^{p-1} \equiv 1 \pmod{p}$ so $a^{p-1}+b^{p-1} \equiv 2 \pmod{p}$.

On the other hand, note that $x+y$ divides $x^{2k+1}+y^{2k+1}$ for all integer $x,y,k$ and $k \ge 0$. Hence,since $p \equiv 3 \pmod{4}$ so $(p-1)/2$ is odd, we obtain $a^2+b^2$ divides $(a^2)^{(p-1)/2}+(b^2)^{(p-1)/2}$. Since $p \mid a^2+b^2$ so $p$ divides $(a^2)^{(p-1)/2}+(b^2)^{(p-1)/2}=a^{p-1}+b^{p-1}$, a contradiction since $a^{p-1}+b^{p-1}\equiv 2 \pmod{p}$ and $p \ge 3$. $\square$

Back to the problem, since $3,7 \equiv 3 \pmod{4}$ are primes so if $7 \mid a^2+b^2$ then $7 \mid a, 7 \mid b$ which means $7^2 \mid a^2+b^2$. Similarly, $3^2 \mid a^2+b^2$. Thus, $441 \mid a^2+b^2$.

If $3\mid(a^2+b^2)$ then $3$ divides both $a$ and $b$, since $-1$ is not a quadratic residue $\!\!\pmod{3}$.
The same applies $\!\!\pmod{7}$. If $21\mid(a^2+b^2)$, from the CRT we get that $3$ and $7$ divide both $a$ and $b$, hence $3^2$ and $7^2$ divide both $a^2$ and $b^2$ and $3^2\cdot 7^2\mid (a^2+b^2)$ as wanted.