$g$ is a primitive root of $p^s$, then all the solutions of the congruence $x^{p-1}\equiv 1 \pmod p^{s}$ are given by $1, g^{p^{s}},\ldots, g^{p^{s}(s-2)}$

Clearly that the given set of solutions fit the congruence, but how do I show any solution of the congruence is in the form as listed?


1 Answer 1


Use Discrete Logarithm,




$\iff x\equiv g^{kp^{s-1}}\pmod{p^s}$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .