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)}$

Question

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.

Answer 1

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