# prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)

#### Alex224

##### New member
Hi, I have a problem in my homework that I am stuck with.
Let there be two natural numbers n,m.
let there be d = greatest common divisor of m and n - gcd(m,n)
and l = least common multiple of m and n - lcm(m,n)
I need to prove that CnXCm isomprphic to ClXCd (Cm Cn Cl Cd are all cyclic groups)

I have tried to see what happens if I look at m and n as products of prime numbers but I am kind of stuck around that idea without knowing where to take it.
I also think I should use the fact that gcd(m,n)*lcm(m,n) = m*n but also, can't figure out where to take it where to take it.
Another thing, if the gcd(m,n) = 1 I know that CmXCn is cyclic and the order of it is mn. I thought maybe this fact could help me somehow (m*n = l*d), but I don't know how, because it is possible that gcd(m,n) > 1

can somebody push me towards the right path to solution?
thanks!

#### GJA

##### Well-known member
MHB Math Scholar
Hi Alex224 ,

Are you still interested in a solution to this problem? I have something worked out and want to make sure you're still interested before doing a write up.

#### Alex224

##### New member
Hi Alex224 ,

Are you still interested in a solution to this problem? I have something worked out and want to make sure you're still interested before doing a write up.
yes I am interested. thank you!

#### GJA

##### Well-known member
MHB Math Scholar
I'm not sure what book you're using or what theorems you my have come across in your studies, so I will quote the two we'll be needing here. Regardless, these are basic theorems for cyclic groups and will very likely be in any textbook you come across.

Theorem 1

If $G$ is a finite cyclic group with order $n$, then $G\cong \mathbb{Z}_{n}.$

Theorem 2

Let $n$ be a positive integer which has prime decomposition $n=p_{1}^{i_{1}}p_{2}^{i_{2}}\cdots p_{k}^{i_{k}}$, where $p_{1}<p_{2}<\ldots < p_{k}.$ Then $$\mathbb{Z}_{n}\cong\mathbb{Z}_{p_{1}^{i_{1}}}\times\mathbb{Z}_{p_{2}^{i_{2}}}\times\cdots\times\mathbb{Z}_{p_{k}^{i_{k}}}.$$

Exercise Proof Sketch

According to Theorem 1, it suffices to prove the exercise using $\mathbb{Z}_{m}$ and $\mathbb{Z}_{n}.$ Let $m$ and $n$ have the following prime decompositions: $m = p_{1}^{i_{1}}\cdots p_{k}^{i_{k}}$ and $n = q_{1}^{j_{1}}\cdots q_{s}^{j_{s}}.$

Case 1: $m$ and $n$ are relatively prime.

This is a short exercise using Theorem 2 above that I will let you try first.

Case 2: $m$ and $n$ are not relatively prime.

Since $m$ and $n$ are not relatively prime, they share prime factors in their decompositions. For the sake of concreteness, suppose they share $r$ common primes, where $1\leq r\leq \min\{k,s\}$. Since multiplication is commutative, we may assume without loss of generality that $p_{1} = q_{1},\ldots, p_{2} = q_{2},\ldots,$ and $p_{r} = q_{r}.$

Now, note that gcd$(m,n) = p_{1}^{*_{1}}\cdots p_{r}^{*_{r}},$ where $*_{t} = \min\{i_{t}, j_{t}\}$ for $1\leq t\leq r,$ and lcm$(m,n) = p_{1}^{**_{1}}\cdots p_{r}^{**_{r}}p_{r+1}^{i_{r+1}}\cdots p_{k}^{i_{k}}q_{r+1}^{j_{r+1}}\cdots q_{s}^{j_{s}},$ where $**_{t}=\max\{i_{t},j_{t}\}$ for $1\leq t\leq r.$

According to Theorem 2, it follows that

$$\mathbb{Z}_{m}\times\mathbb{Z}_{n}\cong \underbrace{\mathbb{Z}_{p_{1}^{i_{1}}}\times\cdots\mathbb{Z}_{p_{r}^{i_{r}}}\times\mathbb{Z}_{p_{r+1}^{i_{r+1}}}\times\cdots\times\mathbb{Z}_{p_{k}^{i_{k}}}}_{\mathbb{Z}_{m}}\times\underbrace{\mathbb{Z}_{p_{1}^{j_{1}}}\times\cdots\mathbb{Z}_{p_{r}^{j_{r}}}\times\mathbb{Z}_{q_{r+1}^{j_{r+1}}}\times\cdots\times\mathbb{Z}_{q_{s}^{j_{s}}}}_{\mathbb{Z}_{n}}\qquad (1).$$ From this point we are nearly done. I will leave it to you to try and use the facts about gcd$(m,n)$ and lcm$(m,n)$ above to rewrite equation (1) using the $p^{*}$ and $p^{**}$ terms. Once you have that, you can apply Theorem 2 above once more to obtain the result you want.

Please let me know if you have any further questions after making an honest attempt of your own. Good luck!

Last edited: