0
$\begingroup$

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?

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

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