2
$\begingroup$

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,

  • 0
    @Chan, see Qiaochu's answer http://math.stackexchange.com/questions/6976/proving-that-an-integer-is-the-n-th-power/6983#6983 and my comment there.2011-04-18

1 Answers 1

1

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?