During studying for a cryptography course, I encountered the following formula in a section about calculating discrete logarithm in a group $\mathbb{Z}_n^*$. Assume that $n= p^e$ for some prime. Let $g$ be the generator of the group.
Then we can do the following to calculate $x = \log_{g}(h)$ in $\mathbb{Z}_n^*$, for some some $h = g^x \in \mathbb{Z}_n^*$
- Transform $x$ into the p-adic representation. $$x = x_0 + x_1 p^1 + x_2 p^2 \dots + x_{e-1} p^{e-1}$$ with $x_i < p$
- Calculate sequentially $x_0, \dots, x_{e-1}$.
The script then claims that $x_0$ is the logarithm of $h^{p^{e-1}}$ to the basis of $g^{p^{e-1}}$ (all calculations $\mod n$), because $$h p^{e-1} = g^{x p^{e-1}} = g^{x_0 p^{e-1}} g^{p^e (x_1 + x_2 p + \dots x_{e-1} p^{e-2})} = (g^{p^{e-1}})^{x_0} \mod n$$
where $g^{p^e (x_1 + x_2 p + \dots x_{e-1} p^{e-2})} = 1 \mod n$ because of Fermat's Theorem. This is what I don't get: Why is the order of the group $\mathbb{Z}_*^n$ equal to $p^e (x_1 + x_2 p + \dots x_{e-1} p^{e-2})$ (this is what would need to be the case to be able to use Fermat's theorem, right?
Also, the script claims that the order of $g^{p^{e-1}}$ is $p$. Why is that?