0
$\begingroup$

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$.

  • 0
    @student.llama $ord_m(a)=k$ means that $k$ is the least positive integer satisfying the congruence $a^k \equiv 1 \pmod {m}$.2012-10-25

1 Answers 1

2

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$