# Math Help - Order

1. ## Order

Let $\text{GCD}(r,s)=1$, $r,s>2$, and suppose $[a^d]_r$ is the order of a mod r, and $[a^e]_s$ is the order of a mod s. Let $m=rs$. Show that $[a^{\text{LCM}[d,e]}]_m$ is the order of a mod m.

So we know:
$r|(a^d-1)\iff a^d\equiv 1 \ (\text{mod r})$
$s|(a^e-1)\iff a^e\equiv 1 \ (\text{mod s})$

Now, what?

2. ## Re: Order

Your notation is terribly confusing. You're saying that $d$ is the order of $a$ mod $r$, and $e$ is the order of $a$ mod $s$, and thus that $lcm(e,d)$ is the order of $a$ mod $rs$?

Hint: use the Chinese remainder theorem. There is an isomorphism $(\mathbb{Z}/rs\mathbb{Z})^* \simeq (\mathbb{Z}/r\mathbb{Z})^* \times (\mathbb{Z}/s\mathbb{Z})^*$.

3. ## Re: Order

Originally Posted by Bruno J.
Your notation is terribly confusing. You're saying that $d$ is the order of $a$ mod $r$, and $e$ is the order of $a$ mod $s$, and thus that $lcm(e,d)$ is the order of $a$ mod $rs$?

Hint: use the Chinese remainder theorem. There is an isomorphism $(\mathbb{Z}/rs\mathbb{Z})^* \simeq (\mathbb{Z}/r\mathbb{Z})^* \times (\mathbb{Z}/s\mathbb{Z})^*$.
I am not sure what do by using the CRT but here is what we have:

$a^d\equiv 1 \ (\text{mod r})$
$a^e\equiv 1 \ (\text{mod s})$

So $a^d+rt=a^e+sb=1$

$a^d+rt\equiv a^e \ (\text{mod s})$

I don't know how I am supposed to proceed.

4. ## Re: Order

Do you know a bit of algebra? What is the order of an element in the direct product of two finite groups?