Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

6 Answers 6

up vote 10 down vote accepted

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

share|improve this answer
    
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

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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