# Prove that $a$ is quadratic residue modulo every prime if and only if $a$ is perfect square [duplicate]

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?

Thanks,

## marked as duplicate by Arturo Magidin, Qiaochu YuanApr 18 '11 at 18:32

• @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). – André Nicolas Apr 18 '11 at 18:23
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)