Scribd Logo
Upload

Welcome to Scribd!

  • 54 views

    Rings Lect 3

    Uploaded by

    Ian Krebs
    The document summarizes the Chinese Remainder Theorem (CRT) and some of its applications: 1) The CRT states that for rings R, S1, S2 and homomorphisms f1: R → S1 and f2: R → S2, the map f: R → S1 ⊕ S2 is an isomorphism whose kernel is the intersection of the kernels of f1 and f2. 2) An abstract version of the CRT shows that if R is a ring with ideals I1, I2 such that I1 + I2 = R, then R/(I1 ∩ I2) is isomorphic to R/I1 ⊕

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Rings Lect 3

    Uploaded by

    Ian Krebs
    54 views4 pages
    The document summarizes the Chinese Remainder Theorem (CRT) and some of its applications: 1) The CRT states that for rings R, S1, S2 and homomorphisms f1: R → S1 and f2: R → S2, the map f: R → S1 ⊕ S2 is an isomorphism whose kernel is the intersection of the kernels of f1 and f2. 2) An abstract version of the CRT shows that if R is a ring with ideals I1, I2 such that I1 + I2 = R, then R/(I1 ∩ I2) is isomorphic to R/I1 ⊕

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document summarizes the Chinese Remainder Theorem (CRT) and some of its applications: 1) The CRT states that for rings R, S1, S2 and homomorphisms f1: R → S1 and f2: R → S2, the map f: R → S1 ⊕ S2 is an isomorphism whose kernel is the intersection of the kernels of f1 and f2. 2) An abstract version of the CRT shows that if R is a ring with ideals I1, I2 such that I1 + I2 = R, then R/(I1 ∩ I2) is isomorphic to R/I1 ⊕

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    54 views4 pages

    Rings Lect 3

    Uploaded by

    Ian Krebs
    The document summarizes the Chinese Remainder Theorem (CRT) and some of its applications: 1) The CRT states that for rings R, S1, S2 and homomorphisms f1: R → S1 and f2: R → S2, the map f: R → S1 ⊕ S2 is an isomorphism whose kernel is the intersection of the kernels of f1 and f2. 2) An abstract version of the CRT shows that if R is a ring with ideals I1, I2 such that I1 + I2 = R, then R/(I1 ∩ I2) is isomorphic to R/I1 ⊕

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 4

    3

    3.1

    The Chinese Remainder Theorem


    Introduction

    In the rst year course we learned about the Division Algorithm and Euclids Algorithm for both the ring of integers Z and polynomial rings over elds, K. We are going to slightly extend these results, proving one of the most versatile theorems of algebra, the Chinese Remainder Theorem.

    3.2

    Abstract version

    Although one of the most important things about the CRT is its eciency and practical use, we start quite abstractly. This deals with rather dull technicalities once and for all, so that when we come to concrete versions we can concentrate on what is interesting. Lemma 3.2.1. Let R, S1 , S2 be rings and let f1 : R S1 and f2 : R S2 be homomorphisms. Then f : R S1 S2 by f : a (f1 (a), f2 (b)) is a homomorphism whose kernel is ker f1 ker f2 . Proof. As the operations on S1 S2 are dened coordinatewise it is trivial to see that f is a homomorphism: for example, f (a + a ) = f1 (a + a ), f2 (a + a ) = f1 (a) + f1 (a ), f2 (a) + f2 (a ) = (f1 (a), f2 (a)) + f1 (a ), f2 (a ) = f (a) + f (a ).

    The kernel of f is ker f = {a | f (a) = 0} = {a | (f1 (a), f2 (a)) = 0 = (0, 0)} = {a | f1 (a) = 0, f2 (a) = 0} = ker f1 ker f2 .

    Lemma 3.2.2. Let R be a ring, and let I1 , I2 R be ideals such that 1 I1 + I2 . Then the map : R R/I1 R/I2 given by : a (a + I1 , a + I2 ) is an onto homomorphism. Proof. By the previous lemma applied to the natural homomorphisms R R/I1 and R R/I2 we have that is a homomorphism. We must prove it is onto, so let (a1 + I1 , a2 + I2 ) be an arbitrary member of the codomain. By hypotheses we know that for some i1 I1 and i2 I2 we have that 1 = i1 + i2 . Consider (key step) the element x = a2 i1 + a1 i2 . Then we have that x + I1 = a2 i1 + a1 i2 + I1 = a1 i2 + I1 = a1 (1 i1 ) + I1 = a1 + I1 as a2 i1 and a1 i1 lie in the ideal I1 . A similar argument deals with the coset modulo I2 , and we get that x has the required image. We now have:

    12

    Theorem 3.2.3 (Abstract CRT). Let R be a ring, and let I1 , I2 R be ideals such that I1 + I2 = R. Then R/(I1 I2 ) R/I1 R/I2 = where the isomorphism is the natural x + (I1 I2 ) (x + I1 , x + I2 ). Proof. We consider the map : R R/I1 R/I2 given by a (a + I1 , a + I2 ). By the rst lemma this is a homomorphism with kernel I1 I2 . As R = I1 + I2 we have that 1 I1 + I2 so we can use the second lemma to get that is onto. Now apply the Isomorphism Theorem to and get the result.

    3.3

    The CRT for Z

    Originally the Chinese Remainder Theorem was the proposition that one could, if a, b are coprime integers, and r, s are any integers, nd a solution to the simultaneous congruences xr (mod a), x s (mod b).

    That is only part of what we are now able to prove. Theorem 3.3.1 (CRT for integers). Let a, b Z have highest common factor 1. Then Z/abZ Z/aZ Z/bZ, = the isomorphism being the natural x + abZ (x + aZ, x + bZ). Proof. By Euclids Algorithm we can nd R, S such that 1 = Ra + Sb, so that Z = aZ + bZ. Also, we have that lcm(a, b) = ab/ hcf(a, b) = ab, so that aZ bZ = abZ. The theorem now follows from the abstract version.

    3.4
    3.4.1

    Applications
    Simultaneous congruences

    The result about simultaneous congruences, that if a, b are coprime integers, and r, s are any integers, then we can nd a solution to the simultaneous congruences xr (mod a), x s (mod b).

    is an easy corollary of our CRT. For consider the pair of cosets (r + aZ, s + bZ); by the CRT there exists a unique coset x + abZ such that (x + aZ, x + bZ) = (r + aZ, s + bZ). Although ne in theory, this is not yet of practical use. How do we nd the solution x? We have answered this implicitly. When we proved the ontoness of the map the key consideration was that we could express 1 = i1 + i2 with i1 I1 and i2 I2 ; then we got x as si1 + ri2 . So in practice, we use the (extended) Euclid Algorithma very ecient processto calculate the integers R and S such that 1 = aR + bS; and the solution we then seek is, as per the proof of our abstract theorem, x = aRs + bSr. 3.4.2 Eulers function

    See problems sheet for an application. 13

    3.4.3

    Speeding up Arithmetic

    Suppose again that a, b Z have highest common factor 1. By the CRT we have that Z/abZ Z/aZ Z/bZ. = We can then carry out arithmetic calculations in Z/abZ in the following way: Step 1 For each input x := x + abZ calculate x := x + aZ and x := x + bZ. Step 2 Carry out the required calculations on the x in Za to get the answer y ; and on the x in Zb to get y . Step 3 Using the inverse of the isomorphism, calculate the value of y which maps to the pair (, x). x Can this possibly be a good idea? The answer is a resounding Yes! Essentially we have some setup costs we must pay once and for all: the calculation of integers R and S such that Ra + Sb = 1 which allow us to compute the inverse isomorphism. This is not very expensive: Euclids algorithm is very fast, requiring O(log a) steps. The reductions of step 1 are not expensive, although an extra overhead. But the savings come in step 2: although we have to carry out the calculations twice we do so in much smaller systems. If we make a careful analysis well see that this really works.

    3.5

    The CRT for K[X]

    If we look at our proof of the CRT for Z we will see that all we needed to use about the ring Z and the elements a, b with hcf(a, b) = 1 were these facts, both consequences of Euclids Algorithm: (i) 1 = Ra + Sb for some R, S; (ii) aZ bZ = abZ. We have the Division Algorithm, highest common factors, and Euclids Algorithm in the ring K[X], where K is any eld; we saw this in the rst-year course. Therefore we have, with no more work to be done: Theorem 3.5.1 (CRT for K[X] ). Let K be a eld and let f (X), g(X) K[X] have highest common factor 1. Then K[X]/f (X)g(X)K[X] K[X]/f (X)K[X] K[X]/g(X)K[X], = the isomorphism being the natural t + f (X)g(X)K[X] (t + f (X)K[X], t + f (X)K[X]).

    3.6

    An application

    There would be no point in this, of course, if there were not important applications.

    14

    3.6.1

    Interpolation

    Suppose we have k + 1 distinct members ai of a eld K; and k + 1 arbitrary members bi of K. We can apply the CRT rst to the polynomials (X a1 ) and i>1 (X ai ), and then inductively and get K[X]/ (X ai )K[X] = K[X]/(X ai )K[X].

    Let us look for a moment at K[X]/(X a)K[X]. What does a coset b + (X a)K[X] represent? It is, as the Remainder Theorem tells us, the set of all polynomials which take the value b at the point a. So what the CRT tells us in part is this: there is a unique coset of polynomials t(X) + (X ai )K[X]

    consisting of those polynomials which take the values bi at the points ai . By the Division Algorithm we can then nd in the coset a unique t(X) of degree at most k with this property. Once again, note that the CRT is actually constructive: Euclids Algorithm lets us compute the inverse of the isomorphism eciently, and nd t(X) from the data (ai , bi ), i = 1, . . . , k + 1.

    15

    You might also like