# Number of quadratic residues

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.

• Try Hensel's Lemma? – universalset Dec 4 '13 at 16:36
• So you are only interested in units? IOW you do not call $9=3^2$ a quadratic residue modulo $27$? – Jyrki Lahtonen Dec 4 '13 at 16:57
• 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. – Jyrki Lahtonen Dec 4 '13 at 16:59
• 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$. – Jyrki Lahtonen Dec 4 '13 at 17:04

## 1 Answer

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}$.