I wouId like to prove that for an odd prime power $p^k$, there are $\frac{\phi(p^k)}{2}$ quadratic residues.

What I have done is that if $u_1$ is a unit, so is $-u_1$, which means it is somewhere in the representative set $\{u_1,\dots,u_{\phi(p^k)}\}$. Group each unit with its negative, so we have $\frac{\phi(p^k)}{2}$ groups. I must show that each group has a distinct square.

This is where I run into trouble. Essentialy what I must show is that $a^2 \equiv b^2 \mod{p^k} \implies a \equiv \pm b \mod{p^k}$

I am not sure how to go about doing this. If it were just a first power I could use Euclid's Lemma, but wit a higher power I'm not sure how to proceed.

  • $\begingroup$ Try Hensel's Lemma? $\endgroup$ – universalset Dec 4 '13 at 16:36
  • $\begingroup$ So you are only interested in units? IOW you do not call $9=3^2$ a quadratic residue modulo $27$? $\endgroup$ – Jyrki Lahtonen Dec 4 '13 at 16:57
  • $\begingroup$ If you do restrict yourself to units, then you could try to study the homomorphism $f:x\mapsto x^2$ from the multiplicative group $\Bbb{Z}_{p^k}^*$ to itself. Can you show that $|\ker f|=2$? What does that tell you about the image? If you haven't done any group theory yet, then this is probably all Greek to you. $\endgroup$ – Jyrki Lahtonen Dec 4 '13 at 16:59
  • $\begingroup$ Which leaves the more elementary alternative: if $a^2\equiv b^2$, then $p^k\mid(a^2-b^2)=(a-b)(a+b)$. Can you show that if $a$ and $b$ are not divisible by $p$, then at most one the factors $(a-b)$, $(a+b)$ is divisible by $p$? With that under your belt you can then conclude that one of them has to be divisible by $p^k$. $\endgroup$ – Jyrki Lahtonen Dec 4 '13 at 17:04

Expanding my comment into an answer:

Fix $b$. We know that $x^2\equiv b^2 \pmod{p}$ has exactly two solutions modulo $p$. Since $p>2$, $2x \not\equiv 0 \pmod{p}$ for $x\not\equiv 0 \pmod{p}$, so the conditions for Hensel's lemma hold, and hence each solution to $x^2 \equiv b^2 \pmod{p}$ corresponds to a unique solution to $x^2\equiv b^2 \pmod{p^k}$. Thus there are exactly two such solutions for any given $b$, and thus the only solutions are $x \equiv \pm b \pmod{p^k}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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