[proofplan] We compute the order of an arbitrary element of the direct product from the orders of its two coordinates. This shows that the largest possible element order is $\operatorname{lcm}(m,n)$, so a cyclic product of size $mn$ forces $\operatorname{lcm}(m,n)=mn$, equivalently $\gcd(m,n)=1$. Conversely, when $\gcd(m,n)=1$, the element $([1]_m,[1]_n)$ has order $mn$ and therefore generates the whole product. The final isomorphism is the explicit reduction map modulo $m$ and modulo $n$. [/proofplan]

[step:Compute element orders in the direct product]For a positive integer $q$, write $[a]_q$ for the residue class of $a \in \mathbb{Z}$ in the additive group $\mathbb{Z}/q\mathbb{Z}$. Let \begin{align*} x := ([a]_m,[b]_n) \in \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}. \end{align*} Let $r := \operatorname{ord}([a]_m)$ and $s := \operatorname{ord}([b]_n)$. Since $m[a]_m=[0]_m$ and $n[b]_n=[0]_n$, the definitions of $r$ and $s$ give $r \mid m$ and $s \mid n$. For $t \in \mathbb{N}$, the equality $t x = ([0]_m,[0]_n)$ holds if and only if $t[a]_m=[0]_m$ and $t[b]_n=[0]_n$. By the definitions of $r$ and $s$, this is equivalent to $r \mid t$ and $s \mid t$. Hence the least positive such $t$ is $\operatorname{lcm}(r,s)$, so \begin{align*} \operatorname{ord}(x)=\operatorname{lcm}(r,s). \end{align*} Since $r \mid m$ and $s \mid n$, every common multiple of $m$ and $n$ is a common multiple of $r$ and $s$. Therefore \begin{align*} \operatorname{ord}(x)=\operatorname{lcm}(r,s) \mid \operatorname{lcm}(m,n). \end{align*}[/step]

[guided]The operation on the direct product is componentwise addition. Thus multiplying \begin{align*} x := ([a]_m,[b]_n) \end{align*} by a positive integer $t$ gives \begin{align*} t x = (t[a]_m,t[b]_n). \end{align*} The identity element of the product is $([0]_m,[0]_n)$, so $t x=([0]_m,[0]_n)$ exactly when both coordinates vanish: \begin{align*} t[a]_m=[0]_m \end{align*} and \begin{align*} t[b]_n=[0]_n. \end{align*} Define \begin{align*} r := \operatorname{ord}([a]_m) \end{align*} and \begin{align*} s := \operatorname{ord}([b]_n). \end{align*} By definition of order, $t[a]_m=[0]_m$ holds exactly when $r \mid t$, and $t[b]_n=[0]_n$ holds exactly when $s \mid t$. Therefore $t x=([0]_m,[0]_n)$ exactly when $t$ is a common multiple of $r$ and $s$. The smallest positive common multiple is $\operatorname{lcm}(r,s)$, hence \begin{align*} \operatorname{ord}(x)=\operatorname{lcm}(r,s). \end{align*} Finally, $m[a]_m=[0]_m$ and $n[b]_n=[0]_n$, so $r \mid m$ and $s \mid n$. Thus every common multiple of $m$ and $n$ is also a common multiple of $r$ and $s$, and the least common multiple of $r$ and $s$ divides the least common multiple of $m$ and $n$: \begin{align*} \operatorname{ord}(x)=\operatorname{lcm}(r,s) \mid \operatorname{lcm}(m,n). \end{align*}[/guided]

[step:Derive coprimality from cyclicity] Assume that $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ is cyclic. Its cardinality is $mn$, so it has an element $x$ with \begin{align*} \operatorname{ord}(x)=mn. \end{align*} By the previous step, \begin{align*} mn \mid \operatorname{lcm}(m,n). \end{align*} Since $mn$ is itself a common multiple of $m$ and $n$, the least common multiple satisfies \begin{align*} \operatorname{lcm}(m,n) \le mn. \end{align*} Therefore $\operatorname{lcm}(m,n)=mn$. Let $d := \gcd(m,n)$. The elementary identity \begin{align*} \gcd(m,n)\operatorname{lcm}(m,n)=mn \end{align*} then gives $d=1$. Hence $\gcd(m,n)=1$. [/step]

[step:Construct a generator when the moduli are coprime] Assume $\gcd(m,n)=1$. Define \begin{align*} g := ([1]_m,[1]_n) \in \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}. \end{align*} The element $[1]_m$ has order $m$, and the element $[1]_n$ has order $n$. By the order computation in the first step, \begin{align*} \operatorname{ord}(g)=\operatorname{lcm}(m,n). \end{align*} Since $\gcd(m,n)=1$, the identity $\gcd(m,n)\operatorname{lcm}(m,n)=mn$ gives \begin{align*} \operatorname{ord}(g)=mn. \end{align*} The product group has exactly $mn$ elements, so the subgroup generated by $g$ has the same cardinality as the whole group. Therefore \begin{align*} \langle g\rangle=\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}. \end{align*} Thus the product is cyclic. [/step]

[step:Define the reduction map and prove it is an isomorphism] Assume $\gcd(m,n)=1$. Define the map \begin{align*} \Phi: \mathbb{Z}/mn\mathbb{Z} &\to \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} \end{align*} by \begin{align*} \Phi([a]_{mn}) := ([a]_m,[a]_n). \end{align*} This map is well-defined: if $[a]_{mn}=[b]_{mn}$, then $mn \mid (a-b)$, so $m \mid (a-b)$ and $n \mid (a-b)$, giving $[a]_m=[b]_m$ and $[a]_n=[b]_n$. For $[a]_{mn},[b]_{mn} \in \mathbb{Z}/mn\mathbb{Z}$, \begin{align*} \Phi([a]_{mn}+[b]_{mn})=\Phi([a+b]_{mn})=([a+b]_m,[a+b]_n). \end{align*} Using addition in each [quotient group](/theorems/790), \begin{align*} ([a+b]_m,[a+b]_n)=([a]_m,[a]_n)+([b]_m,[b]_n)=\Phi([a]_{mn})+\Phi([b]_{mn}). \end{align*} Thus $\Phi$ is a [group homomorphism](/page/Group%20Homomorphism). If $\Phi([a]_{mn})=([0]_m,[0]_n)$, then $m \mid a$ and $n \mid a$. Since $\gcd(m,n)=1$, it follows that $mn \mid a$, so $[a]_{mn}=[0]_{mn}$. Hence $\ker \Phi=\{[0]_{mn}\}$, and $\Phi$ is injective. The domain and codomain both have $mn$ elements, so an injective map between them is surjective. Therefore $\Phi$ is a group isomorphism, and \begin{align*} \mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}. \end{align*} Equivalently, \begin{align*} \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/mn\mathbb{Z}. \end{align*} This proves both directions of the cyclicity criterion and the stated isomorphism in the coprime case. [/step]