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