# $\alpha^{m_1} \equiv \alpha^{m_2} \pmod{p} \Longleftrightarrow m_1 \equiv m_2 \pmod{p - 1}$

A book I'm reading uses the following fact:

$$\alpha^{m_1} \equiv \alpha^{m_2} \pmod{p} \Longleftrightarrow m_1 \equiv m_2 \pmod{p - 1}$$

Here, $$\alpha$$ is a primitive root mod $$p$$. I don't understand why this is true.

I get that $$\alpha$$ being a primitive root means that its powers are uniformly distributed among the $$p - 1$$ integers $$p$$ is coprime to. But, why does that imply $$m_{1} \equiv m_{2}$$ in a different modulus? Can someone please clarify?

• Note: according to Fermat's little theorem, $a^{p-1}\equiv 1\pmod p$ for prime $p$ and $a$ not divisible by $p$ – J. W. Tanner Mar 21 at 15:06
• First note that $\alpha^{p-1}\equiv 1\pmod p.$ So we can restrict to cases $0\leq m_1,m_2<p-1.$ – Thomas Andrews Mar 21 at 15:07
• Yes I know about Fermat's little theorem, but still don't get the results – user651921 Mar 21 at 15:09

$$m_1 \equiv m_2 \pmod{p - 1}$$ means $$m_1-m_2=k(p-1)$$ for some integer $$k$$
so $$\alpha^{m_1} \equiv \alpha^{m_2+k(p-1)}\equiv \alpha^{m_2} \alpha^{k(p-1)}\equiv \alpha^{m_2}\alpha^{(p-1)k}\equiv \alpha^{m_2}1^k\equiv \alpha^{m_2}\pmod p.$$
Conversely, if $$\alpha^{m_1} \equiv \alpha^{m_2}\pmod p$$ and $$\alpha$$ is a primitive root, then $$\alpha^{m_1-m_2}\equiv 1 \pmod p,$$ so $$m_1-m_2$$ is a multiple of $$p-1$$, i.e., $$m_1\equiv m_2 \pmod {p-1}$$.
$$\alpha$$ is a primitive root means $$\alpha$$ has $$\,\color{#C00}{{\rm order} = p-1}.\,$$ Therefore, by a standard Euclidean descent proof $$\,a^{\large n}\equiv 1\iff \color{#c00}{p-1}\mid n.\,$$ OP is the special case $$\,n = m_1-m_2$$