Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|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
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.