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.

Suppose that for some $m\ge1$ and $a$ and $b$ with $\gcd(a,m)=\gcd(b,m)=1$ we have $\operatorname{ord}_ma=k$ and $\operatorname{ord}_mb=l$ where $\gcd(k,l)=1$. Prove that $\operatorname{ord}_m(ab)=kl$.

What I have to go on:

If $(ab)^s \equiv 1 \pmod m$ for some $s \ge 1$, raise both sides of this congruence to the power $k$ and see what this tells you about $s$.

share|improve this question
1  
$ord_m(a)$ means the order of $[a]$ in $(\mathbb{Z}/m)^*$, I guess? –  Martin Brandenburg Oct 25 '12 at 15:06
    
$ord_m(a)=k$ means $a^k \equiv 1 \pmod {m}$. –  student.llama Oct 25 '12 at 15:07
    
@student.llama No. $ord_m(a) = k$ means $k$ is the smallest positive integer such that $a^k \equiv 1 \pmod{m}$. Else, $ord_m(a)$ is not well-defined. –  JavaMan Oct 25 '12 at 15:23
    
@student.llama $ord_m(a)=k$ means that $k$ is the least positive integer satisfying the congruence $a^k \equiv 1 \pmod {m}$. –  juniven Oct 25 '12 at 15:24

1 Answer 1

Let $ord_m{ab}=h\implies (ab)^h\equiv 1\pmod m\implies (ab)^{hk}\equiv 1$

But $a^k\equiv 1\pmod m \implies a^{hk}\equiv 1\implies b^{hk}\equiv 1$

$\implies l\mid hk \implies h$ as $(k,l)=1$ and similarly, $k\mid h\implies kl\mid h$

Now, $a^{kl}\equiv 1$ and $b^{kl}\equiv 1 \implies {ab}^{kl}\equiv 1$ But, $ord_m{ab}=h$ so, $h\mid kl$

Again, $kl\mid h$ So, $ord_m{ab}=h=kl$

share|improve this answer

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.