1. ## Order

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

So we know:
$\displaystyle r|(a^d-1)\iff a^d\equiv 1 \ (\text{mod r})$
$\displaystyle 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 $\displaystyle d$ is the order of $\displaystyle a$ mod $\displaystyle r$, and $\displaystyle e$ is the order of $\displaystyle a$ mod $\displaystyle s$, and thus that $\displaystyle lcm(e,d)$ is the order of $\displaystyle a$ mod $\displaystyle rs$?

Hint: use the Chinese remainder theorem. There is an isomorphism $\displaystyle (\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 $\displaystyle d$ is the order of $\displaystyle a$ mod $\displaystyle r$, and $\displaystyle e$ is the order of $\displaystyle a$ mod $\displaystyle s$, and thus that $\displaystyle lcm(e,d)$ is the order of $\displaystyle a$ mod $\displaystyle rs$?

Hint: use the Chinese remainder theorem. There is an isomorphism $\displaystyle (\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:

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

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

$\displaystyle 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?