# Showing $\mathrm{ord}_d(a) \mid \mathrm{ord}_m(a)$ if $d \mid m$

Let $1\le d$, $1 \le m$ where $d \mid m$. Suppose that $\gcd(a,m)=1$ (and so $\gcd(a,d)=1$). Prove that $\mathrm{ord}_d(a)$ divides $\mathrm{ord}_m(a)$.

-

Let $x=\mathrm{ord}_m(a)$. Then we have $$a^x\equiv 1 \pmod m\implies a^x=mk+1$$ for some $k\in\mathbb{Z}$. Let $m=m'd$. Then $$a^x = mk +1 = d(m'k)+1$$ What can you conclude from this?

-

$a^{ord_d(a)}\equiv 1\pmod d$

Let $a^h \equiv 1\pmod d$ and $ord_d(a)<h=c \cdot ord_d(a) +r$ where $0\le r<ord_d(a)$

So, $a^{c \cdot ord_d(a) +r}\equiv 1\implies a^r\cdot (a^{ord_d(a)})^c\equiv 1$ $\implies a^r\equiv 1$,

So there is one value $r$ of $x$ which $<ord_d(a)$ to satisfy $a^x\equiv 1$, but we know, $ord_d(a)$ is the smallest positive integer value of $x$ , so $r=0\implies ord_d(a)\mid h$

$a^{ord_m(a)}\equiv 1\pmod m$

$\implies a^{ord_m(a)}\equiv 1\pmod d$ as $d\mid m$

$\implies ord_d(a)\mid ord_m(a)$ as here $h=ord_m(a)$

-