Proving That Z_{mn} is Isomorphic to Z_m X Z_nDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/