# Determine the number of solutions of $x^p\equiv 1\mod p^h$ using primitive roots

So the problem is to determine the number of solutions of the congruence $x^p\equiv 1\mod p^h$, where $p$ is an odd prime and $h\geq2$. We are asked to establish the result using primitive roots.

We know that for any primitive root $g_1$ of $p$, $g=g_1+kp$ is, for some $k$, a primitive root mod $p^h$. Also, if $x$ is a solution of the congruence, then there is some $r$ such that $x \equiv g^r \mod p^h$. The congruence then becomes $$(g^r)^p\equiv1\mod p^h,$$ from which we can infer $\phi(p^h)∣rp$. This especially means $p^{h−2}(p−1)∣r$. All in all, we know now that $r$ has to be even and only take values $p^{h−2}(p−1)\leq r\leq p^{h−1}(p−1)$.

I've played around with a few numbers a bit, and found that $r$ likely has to be of the form $kp^{h−2}(p−1)$ for $1\leq k\leq p$, which means that there are exactly $p$ distinct solutions to the congruence, as was expected (by asking WolframAlpha to solve the original congruence). These solutions are given by $$x=g^{kp^{h-2}(p-1)}.$$ We can check this and it looks like it fits.

But I really don't know how to show that the number of solutions is $p$. Why does $r$ have to be of that specific form? That's only a thing I observed but am not able to prove. Any hints would be greatly appreciated

Your work looks sound and you're mostly done! Since $h\ge 2$, from $\phi(p^h)\mid rp$ we have $$rp\equiv 0\pmod{\phi(p^h)} \implies r \equiv 0 \pmod{\frac{\phi(p^h)}{p}}$$ Clearly this congruence admits $p$ incongruent solutions in modulo $\phi(p^h)$, namely : $$r = k\frac{\phi(p^h)}{p},~ 0\le k \lt p$$
The actual $p$ incongruent solutions can be obtained by reducing $g^r$ in modulo $p^h$ $$x\equiv g^r \pmod{p^h}$$
• You have a typo in your first equation, I think ($p$ instead of $r$). I'm following up to the point where you say that the $g^r$ are incongruent mod $p^h$. I assume it's because $g$ is primitive and $0\leq r< \phi(p^h)$, so no residue 'gets hit' twice, right? – Jo Be Mar 20 '15 at 13:54
• Exactly! since $g$ is a primitive root, $g^r$ produces a complete residue set modulo $p^h$ as $r$ ranges from $0$ to $\phi(p^h)$ – ganeshie8 Mar 20 '15 at 13:58