[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*}
[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]
[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]
