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

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search