Proving That Z_{mn} is Isomorphic to Z_m X Z_n

Date: 04/22/2009 at 14:08:23
From: Jameson
Subject: Proving that Zmn isomorphic to Zm X Zn.

If m and n are relatively prime, show that Zmn is isomorphic to Zm X 
Zn.

How do you find [x] when transferring between different modulo?  Is 
the group operation of Zm X Zn circle plus or composition?

I know the bijective mapping f should be [x](mod mn)|-->([x](mod m),
[x](mod n)).  Start by letting [x1](mod mn),[x2](mod mn) be in Zmn. 
Then, f([x1](mod mn) + [x2](mod mn))= f([x1](mod mn)) circle plus f
([x2](mod mn)).  I know that eventually this expression should equal 
f([x1](mod mn)) or f([x2](mod mn)) to prove that they are isomorphic.
 I've seen several proofs using Chinese Remainder 
Theorem and Ring theory, but I have learned neither of these.  How 
do you prove this without these two ways?

Date: 04/25/2009 at 03:46:29
From: Doctor Jacques
Subject: Re: Proving that Zmn isomorphic to Zm X Zn.

Hi Jameson,

In fact, this is equivalent to the Chinese Remainder Theorem (CRT),
although, in this form, the theorem can be generalized to rings other
than Z (using a slightly more general formulation).  This means that
any proof must use some ideas of the CRT and/or ring theory.  I'll
try to make up a simple explanation.

If m is any non-zero integer, there is a ring homomorphism 
g : Z -> Z_m given by g(x) = x (mod m).  This is indeed a 
homomorphism:

  g(x+y) = (x+y) mod m
         = x mod m + y mod m
         = g(x) + g(y)

and

  g(x) = (xy) mod m
       = (x mod m) (y mod m)
       = g(x)g(y)

In the same way, if n is another non-zero integer, we have a
homomorphism h : Z -> Z_n given by h(x) = x mod n.

Now, we can combine these homomorphisms into a single homomorphism
f : Z -> Z_m X Z_n, by defining:

  f(x) = (g(x), h(x))
       = (x mod m, x mod n)

The ring operations on Z_m X Z_n are component-wise addition and
multiplication:

  (a,b) + (c,d) = (a+b,c+d)
  (a,b)(c,d) = (ac,bd)

with a, c in Z_m and b, d in Z_n.

f is also a homomorphism, since:

  f(x+y) = (g(x+y), h(x+y))
         = (g(x)+g(y), h(x)+h(y))
         = (g(x), h(x)) + (g(y), h(y))
         = f(x) + f(y)

with a similar result for multiplication.

Note that:

  f(x + mn) = ((x + mn) mod m, (x + mn) mod n)
            = (x mod m, x mod n)
            = f(x)

and this shows that f(x) only depends on (x mod mn); in other words,
we can consider f as a homomorphism from Z_{mn} to Z_m X Z_n.

It remains to show that f is a bijection from Z_{mn} to Z_m X Z_n.

We first show that f is injective (one-to-one).  A ring homomorphism f
is injective if and only if f(x) = 0 implies x = 0.  Let us assume that:

  f(x) = 0 = (0 mod m, 0 mod n)
       = (x mod m, x mod n)

This means that:

  x = 0 (mod m)
  x = 0 (mod n)

The first congruence shows that x is a multiple of m, and the second
one shows that x is a multiple of n.  As m and n are relatively prime,
we conclude that x is a multiple of mn, which means that x = 0 in
Z_{mn}.  This shows that f is injective.

To show that f is surjective (onto), we must show that, given any two
integers a and b, there exists an integer x such that:

  f(x) = (a mod m, b mod n)

which means:

  x = a  (mod m)          [1]
  x = b  (mod n)

Because m and n are relatively prime, there exist integers u and v
such that:

  um + nv = 1             [2]

These integers can be effectively computed using the Extended
Euclidean Algorithm; if you are not familiar with this, you can search
for these terms in our search page:

  Search Dr. Math
    http://www.mathforum.org/mathgrepform.html 

(or anywhere in the Internet). In particular, this article:

  Euclid's Extended Algorithm
    http://mathforum.org/library/drmath/view/51616.html 

gives a practical way of computing u and v (look at the end).

I claim that the integer:

  x = anv + bmu           [3]

is a solution of the equations [1].  To see this, multiply [2] by a,
this gives:

  aum + anv = a

This shows that anv = a (mod m), and, as bmu is obviously a multiple
of m, we have indeed x = a (mod m), and a similar argument shows that
x = b (mod m).

In summary, f is a ring homomorphism between Z_{mn} and Z_m X Z_n, and
that homomorphism is a bijection; it is therefore an isomorphism.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/