## The Chinese Remainder Theorem (Pt. I)

**Point of Post: **In this post we discuss the Chinese Remainder Theorem and some of its ramifications, in particular, the multiplicativeness of the totient function.

*Motivation*

We now take a break from our theory buidling to discuss a theorem which, while not quite as deep as some other concepts mentioned, has the benefit of being extraordinarily useful. The Chinese Remainder Theorem (often, including in my posts, mercifully abbreviated to CRT) has its beginnings in, where else, China. Namely, people were trying to solve a question of fundamental importance in basic, practical number theory–solving systems of linear congruences. Namely, people were investigating whether given a system of the form

there was a satisfactory solution to both the theoreticians and the pragmatists–or speaking less cryptically, whether there a) exists a solution to the system and is it unique (to some degree) and b) how does one actually find a solution. Or, wreathing this in more sophisticated dressings one is asking whether the map

contains a point in its image. Or, if one is slightly more greedy one can ask if there is such a solution for every such . Thus, we’ve now arrived at the question as to whether is a surjection. So, where does ring theory come into play? Well, tlhe fact that each of the reduction maps is a morphism implies in turn that is a morphism. So, what we know by the first isomorphism theorem is that embeds into . So, what is ? Evidently if then , so . That said, the converse isn’t necessarily true, namely if we restrict to the case when with it’s easy to see that yet . But, when does the converse hold? Namely, when does imply that ? Well, an obvious sufficient condition is that . Thus, if we see that and so, as mentioned before, is an embedding. But, since we may thus conclude that is an isomorphism! Thus, not only have we proven that if the system has a solution for any and that this solution is unique up to the addition of a multiple of but we have also proven that as rings , a fact we only previously knew for groups.

So, as always, we are interested in generalizing concepts true in to larger rings. So, we would like to, in some form, extend the CRT to some broader class of rings. Well, the first step in this would be to translate correctly what the CRT might mean in more general rings. Well, if we translate the above problem precisely (make the transition (for some commutative unital ring ) and (for some ideal of ) then the generalized CRT should seek to answer the following questions about the canonical (coordinate-wise reduction) map : a) what is , b) when is injective, and c) when is surjective. Unfortunately, as is to be expected, these properties (especially that of surjectivity of ) are much more delicate issues than the case for .

*Comaximal Ideals and the CRT*

Let be a ring, and ideals of . We say that are *comaximal *if . Comaximal ideals are also known as coprime ideals, to see why this makes sense we note that for two ideals of we know that if and only if if and only if there exists such that . Thus, the ideals are coprime (comaximal) if and only if are coprime in the normal sense. Thus, it makes sense (considering the motivational example of ) that perhaps comaximality is a sufficient condition for part c) of the CRT above to be true (i.e. that is surjective). Given finitely many ideals of an ideal we say that they are *pairwise comaximal *if, as the name suggests, the pair is comaximal for any . The most relevant property of comaximal ideals is the following:

**Theorem: ***Let be a ring and pairwise comaximal ideals of . Then, and .*

**Proof: **We prove the second statement first. The result is true by assumption for , so assume it’s true for be any ideals. By assumption that there exists some and such that . We see then that for any one has that . Thus, contains both and but this implies that from where the conclusion follows.

With this result we now prove that . Once again, we prove this by induction. It’s obviously true for , and so suppose it’s true for and let are ideals of We see then that . Recall that, in general we have the relations and . But, by the previous paragraph we have that so that this last inclusion becomes . The conclusion follows.

With this result in mind we can finally state the CRT in it’s full generality:

**Theorem (Chinese Remainder Theorem): ***Let be a commutative unital ring and ideals of . Then, if is the natural map given by is a morphism with . Moreover, is injective if and only if and is surjective if and only if are pairwise comaximal.*

**Proof: **Evidently we have that is a morphism with . From this it immediately follows that is injective if and only . The hard part, unfortunately, is the surjectivity condition. So, assume first that are pairwise comaximal. We know then that . So, with this observation we proceed by induction. For we are dealing with the canonical epimorphism which is trivially surjective. So, suppose the result is true for and let be ideals of . Let . By the induction hypothesis and case we can find, for any (thinking of and ) there exists such that and . Since there exists and such that . Consider then that since and one has that

since was arbitrary it follows that is surjective and so the induction is complete.

Conversely, suppose that is surjective. Fix two ideals . We know there exists some such that and . Thus, there exists and such that and and so and so contains the unit and is thus equal to . Since was arbitrary the conclusion follows.

**Corollary: ***Let be a commutative unital ring and comaximal ideals. Then, .*

**References:**

1. Dummit, David Steven., and Richard M. Foote. *Abstract Algebra*. Hoboken, NJ: Wiley, 2004. Print.

[…] The Chinese Remainder Theorem (Pt. II) Point of Post: This is a continuation of this post. […]

Pingback by The Chinese Remainder Theorem (Pt. II) « Abstract Nonsense | September 6, 2011 |

Two typos to fix: “break” instead of “brake” and an extra “whether” in the sentence surrounding equation 1.

Comment by Stephen Tashiro | September 6, 2011 |

Stephen,

Thank you for the corrections! I’m humbled by the fact that you would actually read my posts thoroughly enough to catch such errors–I usually skim.

Best,

Alex

Comment by Alex Youcis | September 6, 2011 |

[…] discussed in a post on ring theory. Namely, from information from recent posts, in particular the Chinese Remainder Theorem we have that thus reducing the problem to finding for primes . This post picks up where the CRT […]

Pingback by The Unit and Automorphism Group of Z/nZ « Abstract Nonsense | September 10, 2011 |

[…] Theorem: Let be a PID and . Then, are coprime if and only if are comaximal. […]

Pingback by PIDs (Pt. II) « Abstract Nonsense | October 22, 2011 |

[…] homomorphism would have to be a common divisor of and , and thus have order one. From this, the Chinese remainder theorem (only the group part), the previous theorem, and the way Hom splits we can easily deduce […]

Pingback by Homomorphisms Between Finitely Generated Abelian Groups (Pt. I) « Abstract Nonsense | November 14, 2011 |

[…] really suffices to compute for since the rest follows by the multiplicativeness of Hom and the Chinese remainder theorem. To make this computation we merely note that we have the exact […]

Pingback by The Hom Functor is Left Exact « Abstract Nonsense | January 30, 2012 |

[…] since splits into distinct linear factors we may conclude then by the Chinese remainder theorem that where –and since the product of fields never has any nonzero nilpotents we may […]

Pingback by Separable Extensions (Pt. II) « Abstract Nonsense | May 4, 2012 |