# Prove that if $r$ is a primitive root modulo $m$, and $(a, m) = (b, m) = 1$, then $r^a \equiv r^b \pmod{m}$ implies $a\equiv b \pmod{\varphi(m)}$

Prove that if $r$ is a primitive root modulo $m$, and $(a, m) = (b, m) = 1$, then $r^a \equiv r^b \pmod{m}$ implies $a \equiv b \pmod{φ(m)}$.

Any hints will be appreciated. Thanks so much.

• Note that the hypotheses that $(a,m)=(b,m)=1$ are completely unnecessary. (Indeed, it never makes sense to consider exponents modulo the modulus.) – Greg Martin Nov 1 '16 at 6:01

As $r$ is a primitive root modulo $m$, then $r^{\varphi(m)}\equiv 1 \pmod{m}$, also $\varphi(m)$ is the less natural number $k$ such that $r^k\equiv 1 \pmod{m}$. This implies that if $r^s\equiv 1 \pmod{m}$, then $\varphi(m)|s$.
By other hand, $r^a\equiv r^b \pmod{m}$. WLOG $a\ge b$ then: $$r^a-r^b\equiv 0 \pmod{m}$$ $$r^b[r^{a-b}-1]\equiv 0 \pmod{m}$$ $$r^{a-b}-1\equiv 0 \pmod{m} \to r^{a-b}\equiv 1 \pmod{m}$$
We can conclude $\varphi(m)|a-b$ this means $a\equiv b \pmod{\varphi(m)}$.
Suppose that $r^{a} - r^{b}$ is a multiple of $m$. This is equivalent to $r^{a-b} - 1$ being a multiple of $m$, since $r$ is co-prime to $m$, so we can remove the $r^b$ out.
Now, by Euler's theorem, $r^{\phi(m)} \equiv 1 \mod m$. However, there is a stronger fact: $\phi(m)$ is in fact the order of $r \mod m$, given that $r$ is a primitive root. Hence, $\phi(m) | (a-b)$ because if it doesn't, then the remainder $d$ of the division would be smaller than $\phi(m)$ and satisfy $r^{d} \equiv 1 \mod m$, and this would contradict the definition of order.
• A quibble: the definition of order only says that $\phi(m) \le (a-b)$. The fact that $\phi(m)$ actually divides $a-b$ is a theorem/lemma about the order, not part of the definition. – Greg Martin Nov 1 '16 at 6:02