# Prove that 1 less than the number of equivalence classes divides $p-1$ where $p$ is prime

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.

• Note it is $m-1$ for a boring reason, $0$ is in an equivalence class all by itself. – André Nicolas Nov 3 '15 at 5:11
• @AndréNicolas, not terribly helpful. Can you tell me any more? – ALannister Nov 3 '15 at 5:13

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$.
• not sure if you're back on MSE, but if you are, could you please explain to me how to even get started on showing that any two equivalence classes of non-zero elements of $\mathbb{Z}_{p}$ have the same number of elements? Thank you. – ALannister Nov 6 '16 at 22:54