The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

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 

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


  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

  (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 

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

  Euclid's Extended Algorithm 

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 
Associated Topics:
College Modern Algebra
College Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.