Invariant factors of $\mathbb Z_m\times\mathbb Z_n$

Prove that the invariant factors of $\mathbb Z_m\times\mathbb Z_n$ are $mn$ if $m$ and $n$ are relatively prime and are the greatest common divisor and the least common multiple of $m$ and $n$ if they are not relatively prime.

-
Hint: use the Chinese Remainder Theorem. –  DonAntonio Nov 22 '12 at 4:43

If $m$ and $n$ are coprime, we know that

$$\mathbb{Z}_{mn} \cong \mathbb{Z}_{m} \times \mathbb{Z}_{n}$$

Since one can easily define an isomorphism from the latter to the former via $\varphi(a,b) = (ab)$ (check that this works).

From this we can deduce that if $n = \prod_{i=1}^k p_{i}^{r_i}$ is the prime factorization of $n$, then

$$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p_{1}^{r_1}\mathbb{Z} \times \cdots \times \mathbb{Z}/p_{k}^{r_k}\mathbb{Z} \,\,\,\,\,\, (*)$$

If $m$ and $n$ are not coprime, we do the following. Let's start with $\mathbb{Z}_m \times \mathbb{Z}_n$. We can break $\mathbb{Z}_m$ and $\mathbb{Z}_n$ as in $(*)$ into the product of the cyclic groups corresponding to their prime factors. We will now "recollect" these terms so we get the product $\mathbb{Z}_{gcd(m,n)}$ and $\mathbb{Z}_{lcm(m,n)}$. Let $\mathbb{Z}/p_{i}^{r_i}$ be one of the groups in this product. If $p$ divides only one of $m,n$ let this group be part of our collection that will form the lcm. Otherwise, if $p$ divides both, so we have two groups of this form, then put the group with the larger power of $p$ into our collection for the lcm, and the other for the collection into the gcd.

Okay, now we have these two collections, and in each collection all the groups are of coprime order. Check that in our "lcm collection" the product of the orders of these groups is indeed the lcm, and since the orders are coprime their product is in fact $\mathbb{Z}_{lcm(m,n)}$ by the first part of this problem. By an identical argument, the product of the groups in the "gcd collection" is $\mathbb{Z}_{gcd(m,n)}$ , so we have

$$\mathbb{Z}_{m} \times \mathbb{Z}_{m} \cong \mathbb{Z}_{lcm(m,n)} \times \mathbb{Z}_{gcd(m,n)}$$

-
Thank you guys so much, is there by any chance a method to do this without the Chinese Remainder Theorem? –  user50291 Nov 25 '12 at 18:27
Yes, I've just rewritten it so that it avoids the Chinese Remainder Theorem. Is this any better? –  Isaac Solomon Nov 25 '12 at 19:24