# 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!

-
As a supplement to the various detailed answers below, the following short remark might help: gcd$(m,n) = 1$ if and only lcm$(m,n) = mn$. It is the latter fact (about the lcm) which is more directly relevant to your problem than the gcd fact (although they are equivalent). Try combining your intuition about "interleaving" with the formal notion of lcm$(m,n)$. –  Matt E Oct 3 '10 at 21:59

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?

-
To try and answer your first question, I observe that I want to raise $(g^a,h^b)$ to a power $x$ such that $xa$ is a multiple of $n$ and $xb$ is a multiple of $m$. Also, the order will be the least such $x$, so I guess we want $x = lcm(m,n)$. Thus the order of $(g^a,h^b)$ is $lcm(m,n)$. Is this correct? –  Martin Lauridsen Oct 3 '10 at 22:11
Not quite. lcm$(m,n)$ certainly works, but it need not be the smallest that works. For example, $g^a$ could have order strictly less than $n$ and $g^b$ have order strictly less than $m$. –  Arturo Magidin Oct 3 '10 at 22:20
But you do know that the order is at most lcm(m,n). Now, you want the possibility for the order to be $mn$ in the case where $G\times H$ is cyclic, so what does that tell you about $m$ and $n$? And for the converse, can you get it at this point? –  Arturo Magidin Oct 3 '10 at 22:29
Well, as was hinted above, if gcd(m,n) = 1 then lcm(m,n) = mn, so I know the order is at most mn. But I dont see how that gets me closer to showing it is exactly mn when gcd(m,n)=1. I think I have the case covered, where gcd(m,n) > 1, by what Ronaldo answered. –  Martin Lauridsen Oct 3 '10 at 22:49
So you know that if $G$ is cyclic, then lcm$(m,n)=1$. Now suppose that lcm$(m,n)=1$, and find an element whose order is exactly lcm$(m,n)=1$. Note that the problem with your argument before is that you did not take into account $a$ and $b$; but you know exactly what the order of $g^a$ is (it is $n/$gcd$(n,a)$), and similarly for $g^b$. So find a specific $a$ and a specific $b$ that give you the order you want. –  Arturo Magidin Oct 3 '10 at 22:55

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.

-

Use these facts:

1) Cyclic groups of the same order are isomorphic.

-

HINT $\rm\quad\ \ gcd(m,n) > 1$

$\rm\quad\iff\ lcm(m,n) < mn$

$\rm\quad\iff\ \mathbb Z_m \times \mathbb Z_n\$ has all elts of order $\rm < mn$

$\rm\quad\iff\ \mathbb Z_m \times \mathbb Z_n\$ is noncyclic

-