An Illustrated Proof: Products of Cyclic Groups

On this page we write a proof that Z_m x Z_n is isomorphic to Z_mn if and only if m and n are relatively prime.  We illustrate the proof with images from Group Explorer.  The intent is to show that Group Explorer can be used to make some nice intuition-strengthening images, and such images can be useful when seeking to appreciate a proof.

Our website also contains another illustrated proof; there we show that a normal subgroup can be used to form a factor group.

Theorem:  For any two positive integers m and n, the product group Z_m x Z_n is isomorphic to Z_mn if and only if m and n are relatively prime.

Proof:  Before we begin the proof, it is worth noting that an arbitrary element of the product group Z_m x Z_n will be of the form <a,b> for some positive integer a between 0 and m-1 and some integer b between 0 and n-1.

First consider the backward direction of the implication.  Assume we have that m and n are relatively prime, and we wish to show that Z_m x Z_n is isomorphic to Z_mn.  We do so by showing that the element <1,1> generates Z_m x Z_n.  That is, we will show that you need to add <1,1> to itself mn times before it will equal <0,0>, the identity of Z_m x Z_n.  We demonstrate this both formally and visually, and we do these two arguments simultaneously.

Consider the group Z4 x Z4.  It is pictured to the right, and examining it gives us a good idea of what products of cyclic groups look like.  That is, they are composed of two (or more) generators, each of which acts completely independently of the other.  That is, if you follow the red arrow two steps and then the light blue arrow two steps, it is the same as if you had done them in the other order, or jumbled up the order to be red, light blue, red, light blue.  Therefore we get the simple grid-like structure we see to the right.  This is discussed further on our page on the Fundamental Theorem of Abelian Groups. Now let's see what the diagonal element <1,1> looks like in that diagram.  Shown here to the right is the same Cayley diagram for Z4 x Z4, except we've removed the old arrows and instead introduced an arrow that represents the element <1,1>.  You can see that the red arrow in the diagram to the right is equivalent to following a red and then a blue in the diagram above it.  Furthermore, you can see that the red arrows in this illustration do not generate the group, because if you follow any one of them for four steps, you get back where you started.  Since there are more than 4 elements in the group, you didn't visit all of them! So the question becomes, "How many times would I have to add <1,1> to itself before I return to the element <0,0>?"  Let's answer the question one dimension at a time.  Let's also look at another example group, Z2 x Z4, pictured in the Cayley diagram to the right. How many times would I have to add <1,1> to itself to get the first coordinate to be 0 (i.e. <0,something>)?  This is what we mean by considering the question one dimension at a time. Let's assume the red arrows correspond to the first coordinate, and the blue arrows to the second. We apply the same tactic as in the last example, here redrawing the same diagram but with only the arrows for <1,1> shown.  The top row consists of all elements of the form <0,x> for some x, and the bottom row consists of all elements of the form <1,x>.  Thus we see that if we add <1,1> to itself 2 times, or 4, or 6, or 8, or any even number, we end up in the top row, <0,something>. Now we consider the other dimension.  How many times would I have to add <1,1> to itself to get the second coordinate to be 0 (i.e. <something,0>)?  The leftmost column in this diagram represents the elements of the form <x,0>, and so we can see that adding <1,1> to itself 4 times returns us to the left column, as would adding it up 8, 12, 16, ... times. Thus we've ended up first listing the multiples of m (2, 4, 6, 8, ...) and then listing the elements of n (4, 8, 12, 16, ...), recalling m and n are from Zm x Zn.  If we want the smallest number in both of these lists (the first time both coordinates reach 0, returning us to the identity) to be mn, then we're asking that the least common multiple of m and n be mn.  This is equivalent to requiring m and n to be relatively prime. In both above examples, the zeroing of both components happened too soon.  It happens too soon in the example to the right also, which is the altered diagram of Z4 x Z6, where m and n are not relatively prime, and yet (unlike earlier examples) neither is a factor of the other. If we want <1,1> to weave completely through the grid in one thread, we need the least common multiple of m and n to be mn (i.e. that m and n are relatively prime).  In the group library, you will find no groups named Zm x Zn for relatively prime m and n, because the theorem we're proving is true, and therefore the group Z3 x Z4 is named Z12 in the group library! The image to the right is a Cayley diagram of Z12 that has been edited so that its generators are a3 and a4, powers of the original generator.  Thus it "looks like" Z3 x Z4. Once we have organized the diagram this way, we can erase the arrows for a3 and a4 and include instead the arrow for their composition, a7, what we would consider <1,1> in Z3 x Z4. Following the red arrow in this diagram, we see that it takes 12 steps to return home to the identity, meaning that is has visited all 12 elements of the group.  Thus the group was cyclic to begin with, and is indeed Z12.

Next consider the forward direction of the implication.  We do this half of the proof without illustrations, but as you will see in the text below, we encourage the reader to envision arbitrary grid-like Cayley diagrams similar to the ones above.

Assume we have that Z_m x Z_n is isomorphic to Z_mn, and we wish to prove that m and n are relatively prime.  Because Z_m x Z_n is isomorphic to Z_mn, we know that it is of size mn.  Again we will make use of the fact that when m and n are relatively prime, their least common multiple is mn.

So assume towards a contradiction that we have a common multiple k of m and n that is smaller than mn.  Take any element <a,b> in Z_m x Z_n.  If we add <a,b> to itself k times, let's think of what it would look like in one of the two-colored rectangular Cayley diagrams above.  We would have used the vertical generator k times, which is a multiple of m and therefore will end us back up in the top row.  We would have used the horizontal generator k times, which is a multiple of n and therefore will end us back up in the left column.  Thus any element <a,b> that you pick will get back to the identity after using it only k times, which is fewer than mn, the size of Z_m x Z_n.  So no element in Z_m x Z_n generates all of the group, which is a contradiction, since we have assumed Z_m x Z_n to be cyclic (isomorphic to Z_mn).  Our assumption therefore must have been wrong--there can be no multiple k of m and n smaller than mn, and so we have m and n relatively prime.