0
$\begingroup$

Showing $\mathrm{ord}_d(a) \mid \mathrm{ord}_m(a)$ if $d \mid m$. Also, let $1\le d$, $1 \le m$, and $\gcd(a,d)=1$.

What I have so far is:

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$

I'm not sure where to go from here.

Thanks,
Brooke

  • 0
    A typographical experiment: $6gcd(a,b)$, $6\gcd(a,b)$. If you see what I see, the second of these has proper spacing between $6$ and $\gcd$ and the first does not. Also the second is not italicized. The first is coded as 6gcd(a,b) and the second as 6\gcd(a,b). The second is standard LaTeX usage. (I changed it in the posted question.)2012-10-15

1 Answers 1

1

Let $O_m$ be the order of $a \pmod{m}$ and $O_d$ the order of $a \pmod{d}$. Since $ a^{O_m}\equiv 1\pmod{m},$ we have $ d|m \quad \mbox{and} \quad m|(a^{O_m}-1), $ so $d$ divides $(a^{O_m}-1)$ and we have: $ a^{O_m}\equiv 1\pmod{d}.$ Suppose now that $O_d\leq O_m$ does not divide $O_m$: $ O_m = k O_d + r,\quad 0 follows. In this case we have: $ 1\equiv a^{O_m} \equiv a^{k O_d+r} \equiv (a^{O_d})^k\,a^r \equiv a^r \pmod{d},$ that is a contradiction, since we cannot have $a^{r}\equiv 1$ for any $r. This proves $O_d | O_m$, QED.