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.

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

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

  • $\begingroup$ 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. $\endgroup$ – ALannister Nov 6 '16 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.