3
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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