$x^m \equiv 1$ (mod p) has $(m,p-1)$ roots Why is the following true?
"$x^m \equiv 1$ (mod p) has $(m,p-1)$ roots."
I know these things which could be relevant:
-$x^{p-1} \equiv 1$ (mod p) for any $(x,p)=1$ by Fermat's Little Theorem
-for any root, the order of the root must divide $m$ by Lagrange's Theorem
-$(\mathbb{Z}/p\mathbb{Z})^{*} $ is cyclic
But still can't put the pieces together.
 A: All equalities I write will be mod $p$ when it's clear that they are.
Assume $x^m = 1$. Then the order of $x$ divides $m$, but also $p-1$ by Fermat's Little theorem, so it divides $gcd(m,p-1)$. 
Conversely, if the order of $x$ divides $gcd(m,p-1)$, then $x^m = 1$. 
Therefore we're just looking for $x$'s whose order divides $gcd(m,p-1)$.
Let $G$ be a cyclic group of order $n$ and let $d|n$. Then the set $H=\{x\in G\mid $ the order of $x$ divides $d\}$ is obviously a subgroup of $G$ (note that $G$ is abelian), so it is a cyclic subgroup. Its exponent is $d$, since its exponent divides $d$, and $G$ being cyclic, there exists $x\in G$ of order precisely $d$. 
In cyclic subgroups, exponent and order coincide, thus $H$ is a cyclic subgroup of order $d$ : it has $d$ elements.
Do you see how this solves the question ?
A: Hint:
In a cyclic group of order $n$, generated by $\zeta$, the order of the element $\zeta^k$ is equal to $\;\dfrac{n}{\gcd(n,k)}$.
A: Using discrete logarithm wrt a primitive root $g$ on $$x^m\equiv1\pmod{p^n}$$ for any positive integer $n$
$m$ind$_gx\equiv0\pmod{\phi(p^n)}$
Now use Linear Congruence Theorem .
