3
$\begingroup$

Problem

Prove that the $\mathrm{ord}_{mn}a = [\mathrm{ord}_ma, \mathrm{ord}_na]$ where $a, m, n$ are relatively prime.

My attempt was,
Let $x = \mathrm{ord}_ma$, $y = \mathrm{ord}_na$, and $z = \mathrm{ord}_{mn}a$. By definition of order, we have $a^x \equiv 1 \pmod{m}$ and $a^y \equiv 1 \pmod{n}$ which implies $(a^{x})^y \equiv 1 \pmod{m}$, and $(a^y)^x \equiv 1 \pmod{n}$. Hence, $a^{xy} \equiv 1 \pmod{m}$ and $a^{xy} \equiv 1 \pmod{n}$. Furthermore, we have $a^{xy}, m, n$ are pairwise relatively prime. Therefore, $a^{xy} \equiv 1 \pmod{mn}$. So if $z$ is the order of $a$ modulo $mn$, then $z$ is the smallest integer such that $a^z \equiv 1 \pmod{mn}$. On the other hand, $z|(xy)$ because $a^{xy} \equiv 1 \pmod{mn}$, which implies $xy = z \cdot k$ for some integers $k$. Next, to satisfy the smallest value that divides $xy$, $k$ must be the greatest common divisor of $x, y$. Hence $z = \dfrac{xy}{(x,y)} = [x,y] \text{ } \square$.

Am I in the right track? Any feedback would be greatly appreciated.

Thank you

3 Answers 3

0

Hint $ $ This is obvious using CRT (Chinese Remainder Theorem). Since $\rm\ (m,n) = 1\ $ we know $\rm\ \mathbb Z/mn\ \cong \mathbb Z/m \times \mathbb Z/n ,\,$ via $\rm\ a_{mn}\: \mapsto\: (a_m,a_n),\:$ with obvious order $\rm\ lcm(o(a_m),o(a_n)),\,$ viz.

$$\rm\ (1,1) = (a_m,a_n)^k = (a_m^k,a_n^k) \iff\ o(a_m),\,o(a_n)\ |\ k\iff lcm(o(a_m),\:o(a_n))\ |\ k\qquad $$

Note especially how this method efficiently simultaneously proves both directions of the proof by exploiting the universal bidirectional $(\!\!\iff\!\!)$ definition of $\rm lcm,$ namely $\rm\ a,b\ |\ c \iff [a,b]\ |\ c$

1

Your solution shows good understanding of the situation, but I think it could be considered technically incomplete. You write "to satisfy the smallest value that divides $xy$." It is clear that what you have in mind is that you are looking for the smallest (positive) number which is a multiple of $x$ and of $y$, and divides $xy$. And you do not explicitly say why you are looking for that smallest multiple, although you certainly could explain if asked. The fact that $x$ and $y$ are the orders of $a$ modulo $m$, $n$ respectively is not used, and needs to be ($a^x \equiv 1 \pmod{m}$ and $a^y \equiv 1 \pmod{n}$ are used, but not the minimality of $x$ and $y$).

The following is a variant of your solution that (in the second part) makes explicit what you had left implicit. In the first part, I will not use the product $xy$, because of personal preference.

Each of $x$ and $y$ divides $[x,y]$. Let $[x,y]=xu=yv$. Then $a^{[x,y]}=(a^x)^u$. But since $a$ has order $x$ modulo $m$, it follows that $a^x\equiv 1 \pmod{m}$, and hence $a^{[x,y]}\equiv 1 \pmod{m}$. In the same way, we can show that $a^{[x,y]}\equiv 1 \pmod{n}$. Since $m$ and $n$ are relatively prime, it follows that $a^{[x,y]}\equiv 1 \pmod{mn}$.

Thus $z$, the order of $a$ modulo $mn$, must divide $[x,y]$. We will show that in fact $z=[x,y]$. Since $a^z \equiv 1 \pmod{mn}$, it follows that $a^z \equiv 1 \pmod{m}$. So the order of $a$ modulo $m$, namely $x$, divides $z$. Similarly, $y$ divides $z$. It follows that $[x,y]$ divides $z$, and hence $[x,y]=z$.

  • 0
    @user6312: Just a way to show my appreciation! By the way, wine is not healthy :)2011-04-25
0

That's exactly right. Well done.

  • 0
    @Chan: That's a good way to go about this. I look forward to hearing from you again.2011-04-25