How many non-zero quadratic residues are there for $p^k$, where $p$ is an odd prime and $k$ a positive integer? How many non-zero quadratic residues are there for $p^k$, where $p$ is an odd prime and $k$ a positive integer?
Hi everyone, just need a bit of help for this practice question, I have proved that for $k=1$ then the number of non-zero quadratic residues is $\frac{p-1}{2}$ (I did this using Fermat's Little Theorem and primitive roots mod p).
It's also clear that if there exists an $x$ which satisfies: $x^2 \equiv a \pmod {p^k}$ 
then it must also satisfy: $x^2 \equiv a \pmod {p}$, I'm also ok with showing the reverse by induction, that if $x^2 \equiv a \pmod {p^k}$ then it also satisfies $x^2 \equiv a \pmod {p^{k+1}}$ 
how can I express  how many quadratic residues there are for $p^k$ in terms of the factorization of $p^k$?
Any help would be greatly appreciated!
 A: We must consider even and odd primes separately.
For $p$ odd, the group of units $(\mathbb{Z}/p^k\mathbb{Z})^\times$ is cyclic of order $p^k-p^{k-1}$.  This is a standard but not entirely trivial result—I can find a reference if you like, but this is the part where you will need something like Hensel's lemma.  It follows that exactly half of the units are squares.  But there may be non-unit squares too, so you will also want to look at elements divisible by $p^2$.  So you will end up with a sum like this: $\frac{p^k - p^{k-1}}{2} + \frac{p^{k-2} - p^{k-3}}{2} + \ldots$
For $p$ even, the group of units $(\mathbb{Z}/2^k\mathbb{Z})^\times$ is a tiny bit more complicated: it's product of a cyclic group of order $2$, and another cyclic group of order $2^{k-2}$ (for $k\geq 3$ anyway; for $k\leq 2$ it is cyclic).  Again, this is not a completely trivial result, the proof is understandable but not immediate.  But you now find that one-quarter of the units, or $2^{k-3}$ of them, are squares.  As before, considering non-units as well gives you a sum: $2^{k-3} + 2^{k-5} + \ldots$, where you need to be careful about the last term or two.
But now that I've written this up, I realize that it is quite possible to get around the technical lemmas; you can determine the number of squares without knowing the exact multiplicative structures.  It goes something like this: Say that $a^2 = b^2 (\operatorname{mod} p^k)$.  Then $(a-b)(a+b)$ is divisible by $p^k$.  Now, you must consider various cases separately.  What if $p^{k-4} | (a-b)$, and $p^4 | (a+b)$?  The point is to figure out how many elements are squares by figuring out how many different elements, when squared, can give you the same result.  Every time you get a repeated square, you know that this lowers the number of distinct squares by 1.
If you do this analysis carefully, you should be able to get the same answer I mentioned above.  
