$g$ is a primitive root of $p^s$, determine the form of all solutions to $x^{p-1} \equiv \pmod p^s$

Question

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

Answer 1

Use Discrete Logarithm,

$(p-1)$ind$_gx\equiv0\pmod{\phi(p^s)}$

$\iff(p-1)$ind$_gx\equiv0\pmod{p^{s-1}(p-1)}$

$\iff$ind$_gx\equiv0\pmod{p^{s-1}}$

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