# Prove that for the primitive root $[g]$ modulo p we have $[g]^m=[g]^n \iff p-1\mid m-n$

Prove that for the primitive root $[g]$ modulo $p$ we have $[g]^m=[g]^n \iff p-1\mid m-n$.

Proof: We know

If $g$ is a primitive $p$-root of unity, then $g^n\equiv 1 \pmod p \iff (p-1)\mid n$. Hence if $n$ is not divisible by $(p-1)$ we have $s_n(p)\equiv 0 \pmod p$. Similarly, If $g$ is a primitive $p$-root of unity, then $g^m\equiv 1 \pmod p \iff (p-1)\mid m$. Hence if $m$ is not divisible by $(p-1)$ we have $s_m(p)\equiv 0 \pmod p$.

Can I use these statements to prove the statement above?

• $g^m \equiv g^n \iff g^{m-n} \equiv 1 \pmod{p}$ Since the order of $g$ is $p-1$, therefore $p-1$ divides $m-n$. – Anurag A Jun 16 '14 at 4:38

We have $g^m = g^n$, so multiply through by $(g^n)^{-1} = g^{-n}$:
$$g^{m-n} \equiv 1 \pmod{p}$$
Since $g$ is a generator of the multiplicative group $\mathbb{Z}_p^\times$, then the above holds $\iff$ $m-n$ is a multiple of $|g| = |\mathbb{Z}_p^\times|= p-1$.
Hint: $\mathbb{Z}_p^{\times}$ is a group and the order of $g$ is $p-1$