POTW Product of Two Finite Cyclic Groups

[Euge]

For each positive integer $m$, let $C_m$ denote a cyclic group of order $m$. Show that for all positive integers $m$ and $n$, there is an isomorphism $C_m \times C_n \simeq C_d \times C_l$ where $d = \operatorname{gcd}(m,n)$ and $l = \operatorname{lcm}[m,n]$.

 

[julian]

Spoiler

A trivial result, proven at the end, is that if $C_m$ denotes a cyclic group then $C_m \times C_n \simeq \mathbb{Z}_m \times \mathbb{Z}_n$ where $\mathbb{Z}_m$ is the cyclic group the group under addition + modulo $m$. So we need only prove the result for $\mathbb{Z}_m$. The product on $\mathbb{Z}_m \times \mathbb{Z}_n$ is defined by:

\begin{align*}
(a \text{ mod } m , b \text{ mod } n) (a' \text{ mod } m , b' \text{ mod } n) = ((a+a') \text{ mod } m , (b+b') \text{ mod } n) .
\end{align*}

where $a \text{ mod } m$ means the remainder of $a$ divided by $m$. Define a map $\varphi : \mathbb{Z}_m \times \mathbb{Z}_n \rightarrow \mathbb{Z}_d \times \mathbb{Z}_l$ by

\begin{align*}
\varphi (a \text{ mod } m , b \text{ mod } n) = ((A a + B b) \text{ mod } d , (C a + D b) \text{ mod } l) .
\end{align*}

where $A,B,C,$ and $D$ are yet to be determined integers.

$\varphi$ is a morphism:

The map $\varphi$ is a morphism as

\begin{align*}
& \varphi (a \text{ mod } m , b \text{ mod } n) \varphi (a' \text{ mod } m , b' \text{ mod } n)
\nonumber \\
& = ((A a + B b) \text{ mod } d , (C a + D b) \text{ mod } l) ((A a' + B b') \text{ mod } d , (C a' + D b') \text{ mod } l)
\nonumber \\
& = ((A (a+a') + B (b+b')) \text{ mod } d , (C (a+a') + D (b+b')) \text{ mod } l)
\nonumber \\
& = \varphi ((a+a') \text{ mod } m , (b+b') \text{ mod } n)
\end{align*}

Ensuring $\varphi$ is well defined:

We require it to be well defined, that is replacing $a$ with $a+km$ and replacing $b$ with $b+k'n$ should result in $A a + B b \rightarrow A a + B b + K d$ and $C a + D b \rightarrow C a + D b + K' l$. This places no constraints on the constants $A$ and $B$. As $l = \dfrac{mn}{d}$ we must choose $C = q \dfrac{n}{d}$ and $D = q' \dfrac{m}{d}$ where $q$ and $q'$ are integers. With this choice the morphism is:

\begin{align*}
\varphi (a \text{ mod } m , b \text{ mod } n) = \left( (Aa+Bb) \text{ mod } d , (qa \frac{n}{d} + q'b \dfrac{m}{d}) \text{ mod } l \right)
\end{align*}

$\varphi$ is a group homomorphism:

We confirm it is a group homomorphism:

Identity: The identity of $\mathbb{Z}_m \times \mathbb{Z}_n$ is $(jm \text{ mod } m , j'n \text{ mod } n)$ for $j$ and $j'$ integers. Then

\begin{align*}
\varphi (jm \text{ mod } m , j'n \text{ mod } n) & = \left( (Ajm+Bj'n) \text{ mod } d , (qjm \frac{n}{d} + q'j'n \dfrac{m}{d}) \text{ mod } l \right)
\nonumber \\
& = (kd \text{ mod } d , k'l \text{ mod } l) .
\end{align*}

Inverse: By definition $a+a^{-1} = j m$ and $b+b^{-1} = j' n$

\begin{align*}
& \varphi (a \text{ mod } m , b \text{ mod } n) \varphi(a^{-1} \text{ mod } m , b^{-1} \text{ mod } n)
\nonumber \\
& = \varphi \left( (a \text{ mod } m , b \text{ mod } n) (a^{-1} \text{ mod } m , b^{-1} \text{ mod } n) \right)
\nonumber \\
& = \varphi ((a+a^{-1}) \text{ mod } m , (b+b^{-1}) \text{ mod } n)
\nonumber \\
& = \left( (A(a+a^{-1})+B(b+b^{-1})) \text{ mod } d , (q(a+a^{-1}) \frac{n}{d} + q'(b+b') \dfrac{m}{d}) \text{ mod } l \right)
\nonumber \\
& = (kd \text{ mod } d , k'l \text{ mod } l) .
\end{align*}

Ensuring $\varphi$ is a group isomorphism:

If we can show the kernel of $\varphi$ is trivial (i.e. only contains the identity element), then $\varphi$ would be injective, and given both groups have the same number of elements (as $mn=dl$) we would have that $\varphi$ a group isomorphism, in other words, the two groups are isomorphic. By choosing $q,q',A$, and $B$ appropriately can we ensure that the kernel of $\varphi$ is trivial? In order for $(a \text{ mod } m , b \text{ mod } n) \in ker \varphi$, $a$ and $b$ must satisfy:

\begin{align*}
Aa+Bb = k d \quad \text{and} \quad q a n + q' b m = k' mn
\end{align*}

From which we have

\begin{align*}
(Aq'm-Bqn) a = (kq'd -Bk' n) m \qquad (*) .
\nonumber \\
(Aq'm-Bqn) b = (Ak'm - kqd) n \qquad (**) .
\end{align*}

Choose $q=-1, q'=1$. By Bezout's identity there exist integers $r$ and $s$ such that $rm+sn = d$. Choose $A=r$ and $B=s$. Then from $(*)$ we have $a = K m$ and from $(**)$ we have $b = K' n$, where $K$ and $K'$ are integers. Therefore, with this choice, the kernel of $\varphi$ is trivial.

Thus,

\begin{align*}
\varphi (a \text{ mod } m , b \text{ mod } n) = \left( (ra+sb) \text{ mod } d , (-a \frac{n}{d} + b \dfrac{m}{d}) \text{ mod } l \right)
\end{align*}

is a group homomorphism with trivial kernel and so we have a group isomorphism. We conclude that $\mathbb{Z}_m \times \mathbb{Z}_n \simeq \mathbb{Z}_d \times \mathbb{Z}_l$.Finally:

Spoiler: $C_m \times C_n \simeq \mathbb{Z}_m \times \mathbb{Z}_n$

The $mth$ cyclic group $C_m$ with elements

\begin{align*}
C_m = \langle g \rangle = \{ g^0 , g^1 , g^2 , \dots g^{m-1} \}
\end{align*}

and the powers $g^k$ are distinct for $0 \leq k < m$ with $g^m=e$. With multiplication defined by

\begin{align*}
g^i * g^j = \left\{
\begin{matrix}
g^{i+j} & \text{if } 0 \leq i+j < m, \\
g^{i+j-m} & \text{if } m \leq i+j < 2m - 2
\end{matrix}
\right.
\end{align*}

Define

\begin{align*}
C_n = \langle h \rangle = \{ h^0 , h^1 , h^2 , \dots h^{n-1} \}
\end{align*}

and the powers $k^k$ are distinct for $0 \leq k < n$. Define

Define $\varphi : \mathbb{Z}_m \times \mathbb{Z}_n \rightarrow C_m \times C_n$ by $\varphi (i,j) = (g^i , h^j)$.

Injective: Let $i,i' \in \mathbb{Z}_m$ and $j,j' \in \mathbb{Z}_m$ and assume that $\varphi (i,j) = \varphi (i',j')$. Then $(g^i , h^j) = (g^{i'} , h^{j'})$ and, since powers $g^i$ with $i \in \mathbb{Z}_m$ distinct, it follows that $i = i'$. Similarly, $j = j'$. Hence, $\varphi$ is injective.

Surjective: Let $x \in C_m \times C_n$, we have $x = (g^i , h^j)$ for some $(i,j) \in \mathbb{Z}_m \times \mathbb{Z}_n$. Then $\varphi (i,j) = (g^i , h^j) = x$. Hence, $\varphi$ is surjective.

Homomorphism: Let $(i,j) , (i',j') \in \mathbb{Z}_m \times \mathbb{Z}_n$. Note $i+j = pm + r$ where $0 \leq r \leq m-1$ and Note $i'+j' = qn + r'$ where $0 \leq r' \leq n-1$

\begin{align*}
\varphi ((i+i') \text{ mod m} , (j+j') \text{ mod n}) & = (g^r , h^{r'})
\nonumber \\
& = (g^{i+j - pm} , h^{i'+j'-qn})
\nonumber \\
& = (g^i , h^j) (g^{i'} , h^{j'})
\nonumber \\
& = \varphi (i , j) \varphi (i' , j') ,
\end{align*}

so $\varphi$ satisfies the homomorphism property.

Therefore, $\varphi : \mathbb{Z}_m \times \mathbb{Z}_n \rightarrow C_m \times C_n$ is an isomorphism. We conclude that $\mathbb{Z}_m \times \mathbb{Z}_n \simeq C_m \times C_n$ and hence $C_m \times C_n \simeq \mathbb{Z}_m \times \mathbb{Z}_n$.