Possible Duplicate:
Proving that an integer is the $n$ th power

Prove that $a$ is quadratic residue modulo every prime if and only if $a$ is perfect square

My attempt was,

Since $a$ is perfect square, there exists a $y$ such that $a = y^2$. So, we must show that $x^2 \equiv y^2 \pmod{p}$ for every $p$. We have, $$x^2 - y^2 \equiv 0 \pmod{p}$$ $$(x-y)(x+y) \equiv 0 \pmod{p}$$.

Since $y$ is integer and can be calculated, we only need to solve for $x$ such that $x-y = k.p$ or $x+y = k.p$. In either case, if $p|y$, then $x = 0$ is a solution, otherwise, $(y, p) = 1$, which reduce to the diophantine equation of the form $ax + by = 1$, which is solvable. Hence, we can always solve for $x$ such that $x = y + k.p$ which implies that $x$ is quadratic residue for every prime $p$.

Am I in the right track? Any idea?



marked as duplicate by Arturo Magidin, Qiaochu Yuan Apr 18 '11 at 18:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ See math.stackexchange.com/questions/6976/… $\endgroup$ – Arturo Magidin Apr 18 '11 at 18:19
  • $\begingroup$ @Arturo Magidin: Thanks for the link. $\endgroup$ – Chan Apr 18 '11 at 18:23
  • $\begingroup$ @Chan: You are not on the right track. You need to prove (i) If $a \ne 0$ is a perfect square, it is a QR of every prime and (ii) If $a$ is a QR of every prime, then $a$ is a perfect square. You have only attacked (i), awkwardly. (i) is trivial, if $a$ is non-zero and is equal to $b^2$, then $a \equiv b^2 \pmod{p}$ for every $p$, so it is a QR of every $p$. Now you need to attack the quite a bit harder (ii). $\endgroup$ – André Nicolas Apr 18 '11 at 18:23
  • $\begingroup$ @user6312: :( Sadly I was wrong. But thanks for pointing that out. I will try a bit harder later. Thank you. $\endgroup$ – Chan Apr 18 '11 at 18:30
  • $\begingroup$ @Chan: It would be perfectly OK to not be able to do what I called (ii), it really is extremely hard for someone beginning Number Theory. But you should have seen the logic of the problem, that you needed to show (i) and (ii), and should have seen that (i) was obvious from the definition of QR. $\endgroup$ – André Nicolas Apr 18 '11 at 18:55

If $a=y^2$ then $a\equiv y^2 \pmod{p}$ for every prime $p$, so by definition it is a quadratic residue. (Recall the definition: "An integer $q$ is called a quadratic residue modulo $n$ if it is congruent to a perfect square $\pmod{n}$." This is from Wikipedia)

The other direction is more interesting, what have you tried?


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