0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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