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

  • 1
    $\begingroup$ 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? $\endgroup$ – Jo Be Mar 20 '15 at 13:54
  • $\begingroup$ Ahh good catch! fixed... please check if it is okay now $\endgroup$ – ganeshie8 Mar 20 '15 at 13:54
  • $\begingroup$ 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)$ $\endgroup$ – ganeshie8 Mar 20 '15 at 13:58
  • $\begingroup$ Ok, that's all I needed to know, then. Thank you very much! $\endgroup$ – Jo Be Mar 20 '15 at 13:58

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.