Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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.) – Michael Hardy Oct 15 '12 at 16:27
up vote 1 down vote accepted

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<r<O_d $$ 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<O_d$. This proves $O_d | O_m$, QED.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.