Return to Theorems, Glossary, Homework Problems.

**Statement:**

The group $\mathbb{Z}_m \times \mathbb{Z}_n$ is cyclic and is isomorphic to $\mathbb{Z}_{mn}$ if and only if $m$ and $n$ are relatively prime, that is, the gcd of $m$ and $n$ is $1$.

**Proof:**

Consider the cyclic subgroup of $\mathbb{Z}_m \times \mathbb{Z}_n$, generated by $(1,1)$ as described by Theorem 5.17. As our previous work has shown, the order of this cyclic subgroup is the smallest power of $(1,1)$ that gives the identity $(0,0)$. Here taking a power of $(1,1)$ in our additive notation will involve adding $(1,1)$ to itself repeatedly. Under addition by components, the first component $1 \in \mathbb {Z}_m$ yields $0$ only after $m$ summands, $2m$ summands, and so on, and the second component $1 \in \mathbb{Z}_n$ yields $0$ only after $n$ summands, $2n$ summands, and so on. For them to yield $0$ simultaneously, the number of summands must be a multiple of both $m$ and $n$. The smallest number that is a multiple of both $m$ and $n$ will be $mn$ if and only if the gcd of $m$ and $n$ is $1$; in this case, $(1,1)$ generates a cyclic subgroup of order $mn$, which is the order of the whole group. This shows that $\mathbb{Z}_m \times \mathbb{Z}_n$ is cyclic of order $mn$, and hence isomorphic to $\mathbb{Z}_{mn}$ if $m$ and $n$ are relatively prime.

For the converse, suppose that the gcd of $m$ and $n$ is $d > 1$. Then $mn/d$ is divisible by both $m$ and $n$. Consequently, for any $(r,s)$ in $\mathbb{Z}_m \times \mathbb{Z}_n$, we have

Hence no element $(r,s)$ in $\mathbb{Z}_m \times \mathbb{Z}_n$ can generate the entire group, so $\mathbb{Z}_m \times \mathbb{Z}_n$ is not cyclic and therefore not isomorphic to $\mathbb {Z}_{mn}$.