# If $(\mathrm{ord}_na,\mathrm{ord}_nb)=1$ then $\mathrm{ord}_n(ab) = (\mathrm{ord}_na)(\mathrm{ord}_nb)$

The question I've encountered reading a textbook is as follows:

Show that if $n \in \mathbb{Z}_+$ and $a, b\in\mathbb{Z}$ have $(a,n)=(b,n) = (\mathrm{ord}_na,\mathrm{ord}_nb)=1$ then $\mathrm{ord}_n(ab) = (\mathrm{ord}_na)(\mathrm{ord}_nb)$

I appreciate any help. Thanks.

-
What is $ordna$? –  azarel Mar 18 '12 at 23:55
I could not figure out how to have subscripts, but ordna is the notation for the order of a modulo n. Likewise ordnb is the order of b modulo n. –  Mike Mar 18 '12 at 23:57
Thank you Arturo for editing this up nicely! –  Mike Mar 18 '12 at 23:58
Requests belong in the body, not the title. –  Arturo Magidin Mar 19 '12 at 0:08

Lemma 1. If $A$ is an abelian group, $a,b\in A$, then the order of $ab$ divides the least common multiple of the orders of $a$ and of $b$.

Proof. Let $m$ be the least common multiple of the orders of $a$ and $b$. Then $a^m = b^m = 1$ (since $m$ is a multiple of the order), so $(ab)^m = a^mb^m = 1$. Thus, the order of $ab$ divides $m$. $\Box$

Lemma 2. If $A$ is an abelian group, $a,b\in A$, and $\langle a\rangle\cap\langle b\rangle = \{1\}$, then the order of $ab$ is equal to the least common multiple of the orders of $a$ and of $b$.

Proof. Let $k$ be an integer such that of $(ab)^k=1$. Then $(ab)^k = a^kb^k = 1$, hence $a^k = b^{-k}$. Therefore, $a^k,b^{-k}\in\langle a\rangle\cap\langle b\rangle =\{1\}$. So the order of $a$ divides $k$, and the order of $b$ divides $k$; thus, the lcm of the orders divides $k$. In particular, the lcm of the orders divides the order of $ab$, and by Lemma 2, the order of $ab$ divides the lcm. Thus, the order of $ab$ equals the lcm of the orders. $\Box$

Lemma 3. If $A$ is an abelian group, and $a$ and $b$ have relatively prime orders, then $\langle a\rangle\cap\langle b\rangle = \{1\}$.

Proof. If $x\in \langle a\rangle\cap\langle b\rangle$, then $x=a^i = b^j$ for some $i$ and $j$. Thus, the order of $x$ divides the order of $a$ and the order of $b$, hence it divides the gcd of the order; but since the orders are relatively prime, the gcd is $1$. Thus, $x$ is of order $1$, hence $x=1$. $\Box$

-
Thank you for your help. I was missing these important lemmas. I can see now that lemma 1 helps show that ordn(ab) divides ordn(a)*ordn(b), and lemma 2 helps show that ordn(a)*ordn(b) divides ordn(ab). In lemma 3 I also noticed that in the second sentence you say order of d, should it be b? Thanks again for all your help, this was truly an educational answer. –  Mike Mar 19 '12 at 0:26
@Mike: Yes; that should be a $b$. –  Arturo Magidin Mar 19 '12 at 1:06