I am faced with the following problem:
Let $p$ be a prime number and $\gcd(p,n)=1$. Define an equivalence relation on $\mathbb{Z}_{p}$ as follows: $x \sim y$ iff $n^{r}x = n^{t}y$ for some $r,t \geq 0$. Let $m$ be the number of equivalence classes of this equivalence relation. Prove that $m-1$ is a divisor of $p-1$.
I must admit that I am at a loss as even where to begin with this one: the only thing I know for certain is that $m-1$ is certainly not a divisor of $p$! (Unless of course, $m-1$ is equal to either $1$ or $p$). Well, that and that since there are $m$ equivalence classes, one of them must be $[m-1]$.
I even tried working backwards, saying to myself okay, if $m-1|p-1$, then $\exists c$ such that $p-1 = c(m-1)\, \to \, p = cm-c+1$. But that also doesn't seem to get me anywhere.
It seems as though I have been staring at this forever with nothing to show for it. Thus, any assistance anyone out there could give me would be greatly appreciated.
Outline: The solution below uses group-theoretic ideas, but tries to avoid using group-theoretic language.
Note first that $x\sim 0$ if and only if $x=0$. So if there are $m$ equivalence classes, the non-zero elements of $\mathbb{Z}_p$ are divided into $m-1$ equivalence classes.
Show next that any two equivalence classes of non-zero elements of $\mathbb{Z}_p$ have the same number of elements. That will complete the proof, since if each equivalence class of non-zero elements has size $k$, then $k(m-1)=p-1$.
The equivalence class of $1$ is the set (modulo $p$) of all the powers of $n$. Call this set $K$. Now show that if $x$ is non-zero, then $x\sim y$ if and only if $xy^{-1}$ is in $K$.