# 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!

-
Do you know what Hansel's lemma is? Not necessary, but could be useful. – Calvin Lin Oct 18 '13 at 1:57
Hi Calvin, I have heard of it, but we haven't covered that in my class, do you know of a way around it? Thanks! – JackReacher Oct 18 '13 at 2:17

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.

-
Hi, many thanks for your answer. Your answer really helped me build my intuition to realise that the answer is in fact the Euler Phi Function of $p^k$/2. – JackReacher Oct 19 '13 at 11:47
@mathstudent Glad that you found it helpful. Just to be clear: that's the number of squares not divisible by $p$, and that only works when $p$ is odd. – Slade Oct 19 '13 at 18:25
I think we are talking about the same thing? that the number of quadratic residues for the power of an odd prime is given by $\frac{\phi(p^k)}{2}$? – JackReacher Oct 20 '13 at 5:22
@mathstudent Not so. For instance, $\phi(9)/2 = 3$, but there are 4 quadratic residues $\operatorname{mod}9$: $0,1,4,7$. And $0$ is not the only problem: $\phi(27)/2=9$, but there are $11$ quadratic residues $\operatorname{mod}27$—you are not counting either $0$ or $9$. What $\phi(p^k)/2$ counts is the number of quadratic residues $\operatorname{mod}p^k$ which are relatively prime to $p$. – Slade Oct 20 '13 at 8:48
@mathstudent Keep in mind, $\phi(p^k) = p^k-p^{k-1}$. So $\phi(p^k)/2$ is exactly the first term in the sum I gave in my post. – Slade Oct 20 '13 at 8:52