Product of two cyclic groups is cyclic iff their orders are co-prime
Say you have two groups $G = \langle g \rangle$ with order $n$ and $H = \langle h \rangle$ with order $m$. Then the product $G \times H$ is a cyclic group if and only if $\gcd(n,m)=1$.
I can't seem to figure out how to start proving this. I have tried with some examples, where I pick $(g,h)$ as a candidate generator of $G \times H$. I see that what we want is for the cycles of $g$ and $h$, as we take powers of $(g,h)$, to interleave such that we do not get $(1,1)$ until the $(mn)$-th power. However, I am having a hard time formalizing this and relating it to the greatest common divisor.
Any hints are much appreciated!
$\begin{align}{\bf Hint}\ \ \ & \Bbb Z_m \times \mathbb Z_n\ \text{is noncyclic}\\[.2em] \iff\ & \Bbb Z_m \times \Bbb Z_n\ \text{has all elts of order} < mn\\[.2em] \iff\ & {\rm lcm}(m,n) < mn\\[.2em] \iff\ & \!\gcd(m,n) > 1 \end{align}$
Note that $|G\times H|=|G||H|=nm$; so $G\times H$ is cyclic if and only if there is an element of order $nm$ in $G\times H$.
In any group $A$, if $a,b\in A$ commute with one another, $a$ has order $k$, and $b$ has order $\ell$ then the order of $ab$ will divide lcm$(k,\ell)$ (prove it).
Now take an element of $G\times H$, written as $(g^a,h^b)$, where $G=\langle g\rangle$, $H=\langle h\rangle$, $0\leq a\lt n$, $0\leq b\lt m$. Then $(g^a,h^b)=(g^a,1)(1,h^b)$. In this case, what is the order? Under what conditions can you get an element of order exactly $nm$, which is what you need?
The order of $G\times H$ is $n.m$. Thus, $G\times H$ is cyclic iff it has an element with order $n.m$. Suppose $gcd(n.m)=1$. This implies that $g^m$ has order $n$, and analogously $h^n$ has order $m$. That is, $g\times h$ has order $n.m$, and therefore $G\times H$ is cyclic.
Suppose now that $gcd(n.m) >1$. Let $g^k$ be an element of $G$ and $h^j$ be an element of $H$. Since the lowest common multiple of $n$ and $m$ is lower than the product $n.m$, that is, $lcm(n,m) < n.m$, and since $(g^k)^{lcm(n,m)} = e_{G}$, $(h^j)^{lcm(n,m)} = e_{H}$, we have $(g^k\times h^j)^{lcm(n,m)} = e_{G\times H}$. It follows that every element of $G\times H$ has order lower than $n.m$, and therefore $G\times H$ is not cyclic.