# Prove $7|x^2+y^2$ iff $7|x$ and $7|y$

The question is basically in the title: Prove $7|x^2+y^2$ iff $7|x$ and $7|y$

I get how to do it from $7|x$ and $7|y$ to $7|x^2+y^2$, but not the other way around.

Help is appreciated! Thanks.

-
Have you considered the remainders that $x^2$ leaves modulo 7? – Vincent Tjeng Apr 18 '13 at 14:37
This is a small problem, so you should consider the brute force method of checking all the alternatives before asking for help. Some obvious reductions help: If one of $x,y$ is divisible by seven so must the other. Also the symmetries $x\leftrightarrow -x$, $y\leftrightarrow-y$, $x\rightarrow y$ cut the number of remaining cases down from 36 to 6. Not hard. – Jyrki Lahtonen Apr 18 '13 at 15:16

$x^2,y^2$ can be $0^2\equiv0, (\pm1)^2\equiv1,(\pm2)^2\equiv4, (\pm3)^2\equiv2\pmod 7$

Observe that for no combination except $0,0$ of $x^2+y^2 \equiv0\pmod 7$

Alternatively,

If $(7,xy)=1, x^2+y^2\equiv0\pmod 7\implies \left(\frac xy\right)^2\equiv-1\pmod 7$

But we know $-1$ is a Quadratic residue $\pmod p$ iff prime $p\equiv 1\pmod 4$

-
Thank you. And thank you all - you guys opened my eyes to many ways of solving the one problem I never would've seen with the lecturer I have being very brief with the content. – user73229 Apr 18 '13 at 21:58
Sir you proved that $x^2+y^2$ is divisible by 7 if $7|x$ and $7|y$. But since it is an if and only if so you must also prove that when $7|x$ and $7|y$ then $7|x^2+y^2$. If I'm making any mistake then kindly correct me. – Singh Jun 19 '15 at 15:34
@Singh, If $7|x, x=7m$ where $m$ is any integer – lab bhattacharjee Jun 19 '15 at 17:37

This is a more general fact.

To quote wikipedia:
If $p$ is prime and $p ≡ 3 \pmod 4$ the negative of a residue modulo $p$ is a nonresidue and the negative of a nonresidue is a residue.

Therefore for $p$ is prime with $p ≡ 3 \pmod 4,$ $p\mid x^2+y^2\iff p\mid x$ and $p\mid y$.

-

$x^2+y^2 \equiv \mod 7 \implies x^2 \equiv k \mod 7$ and $y^2 \equiv 7-k \mod 7$

And any $a^2 \equiv 0,1,4,2\mod 7$(Why?) $\implies k=0$

-

Hint $\rm\ mod\ 7\!:\ x,y\not\equiv 0,\ \ x^2 \equiv -y^2\ \stackrel{cube}{\Rightarrow}\, 1\equiv x^6\equiv -y^6\equiv -1\:\Rightarrow\Leftarrow,\$ via little Fermat.

-

It's a matter of modular arithmetic. If $a|b$, then $b\equiv 0 \pmod{a}$. So you know that

$$x^2+y^2 \equiv 0 \mod 7$$ You wish to show that there are no other values of $x$ and $y$ that will satisfy this. One approach is, as lab bhattacharjee notes, direct evaluation of the possibilities. Alternatively, you can suppose that $y\equiv nx\pmod{7}$ for some integer $n$. Then we have $$x^2(1+n^2)\equiv 0 \mod 7$$ Therefore, if $x\not\equiv 0\pmod7$, then we must have that $$n^2\equiv -1 \mod 7$$ However, there is no integer $n$ satisfying this condition. Therefore, $x\equiv 0\pmod7$. And since $y\equiv nx\equiv0\pmod7$, we have that $7|x$ and $7|y$.

-

In $\mathbb{Z}[i]$, $7$ divides $x^2+y^2=(x+iy)(x-iy)$. Therefore, there exists $a+ib \in \mathbb{Z}[i]$ such that $x+iy=7(a+ib)$ or $x-iy=7(a+ib)$. You deduce that $7$ divide $x$ and $y$ in $\mathbb{Z}$.

-