Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
    
Welcome to math.SE: since you are fairly new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are so far; this will prevent people from telling you things you already know, and help them write their answers at an appropriate level. If this is homework, please add the [homework] tag; people will still help, so don't worry. Also, many find the use of imperative ("Find", "Show") to be rude when asking for help; please consider rewriting your post. –  Arturo Magidin Mar 18 '12 at 23:59
    
Requests belong in the body, not the title. –  Arturo Magidin Mar 19 '12 at 0:08
add comment

1 Answer

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.