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,

  • 3
    See http://math.stackexchange.com/questions/6976/proving-that-an-integer-is-the-n-th-power2011-04-18
  • 0
    @Arturo Magidin: Thanks for the link.2011-04-18
  • 0
    @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).2011-04-18
  • 0
    @user6312: :( Sadly I was wrong. But thanks for pointing that out. I will try a bit harder later. Thank you.2011-04-18
  • 0
    @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.2011-04-18
  • 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?