Abstract Nonsense

Crushing one theorem at a time

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.

\text{ }

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

\text{ }

\displaystyle \left\{\begin{array}{c}x\equiv a_1\text{ mod }n_1\\ \vdots\\ x\equiv a_m\text{ mod }n_m\end{array}\right\}\quad\mathbf{(1)}

\text{ }

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

\text{ }

f:\mathbb{Z}\to \mathbb{Z}_{n_1}\times\cdots\times\mathbb{Z}_{n_m}:x\mapsto (x\text{ mod }n_1,\cdots,x\text{ mod }n_m)

\text{ }

contains a point p\in\mathbb{Z}_{n_1}\times\cdots\times\mathbb{Z}_{n_m} in its image. Or, if one is slightly more greedy one can ask if there is such a solution for every such p. Thus, we’ve now arrived at the question as to whether f is a surjection. So, where does ring theory come into play? Well, tlhe fact that each of the reduction maps \mathbb{Z}\to\mathbb{Z}_{n_k} is a morphism implies in turn that f is a morphism. So, what we know by the first isomorphism theorem is that \mathbb{Z}/\ker f embeds into \mathbb{Z}_{n_1}\times\cdots\times\mathbb{Z}_{n_m}. So, what is \ker f? Evidently if x\in(n_1\cdots n_m) then f(x)=0, so (n_1\cdots n_ m)\subseteq \ker f. That said, the converse isn’t necessarily true, namely if we restrict to the case when m=2 with n_1=2,n_2=4 it’s easy to see that f(4)=0 yet 4\notin (8). But, when does the converse hold? Namely, when does n_1,\cdots,n_m\mid x imply that n_1\cdots n_m\mid x? Well, an obvious sufficient condition is that (n_1,\cdots,n_m)=1. Thus, if (n_1,\cdots,n_m)=1 we see that \ker f=(n_1\cdots n_m) and so, as mentioned before, f:\mathbb{Z}/(n_1\cdots n_m)\to \mathbb{Z}_{n_1}\times\cdots\times\mathbb{Z}_{n_m} is an embedding. But, since \left|\mathbb{Z}/(n_1\cdots n_m)\right|=\left|\mathbb{Z}_{n_1}\times\cdots\times\mathbb{Z}_{n_m}\right| we may thus conclude that f is an isomorphism! Thus, not only have we proven that if (n_1,\cdots,n_m)=1 the system \mathbf{(1)} has a solution for any a_1,\cdots,a_m and that this solution is unique up to the addition of a multiple of n_1\cdots n_m but we have also proven that as rings \mathbb{Z}/(n_1\cdots n_m)\cong\mathbb{Z}_{n_1}\times\cdots\mathbb{Z}_{n_m}, a fact we only previously knew for groups.

\text{ }

So, as always, we are interested in generalizing concepts true in \mathbb{Z} 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 \mathbb{Z}\to R (for some commutative unital ring R) and (n_k)\to\mathfrak{a}_k (for some ideal \mathfrak{a}_k of R) then the generalized CRT should seek to answer the following questions about the canonical (coordinate-wise reduction) map \phi:R\to R/\mathfrak{a}_1\times\cdots\times\mathfrak{a}_m: a) what is \ker \phi, b) when is \phi injective, and c) when is \phi surjective. Unfortunately, as is to be expected, these properties (especially that of surjectivity of \phi) are much more delicate issues than the case for \mathbb{Z}.

\text{ }

Comaximal Ideals and the CRT

Let R be a ring, and \mathfrak{a},\mathfrak{b} ideals of R. We say that \mathfrak{a},\mathfrak{b} are comaximal if \mathfrak{a}+\mathfrak{b}=R. Comaximal ideals are also known as coprime ideals, to see why this makes sense we note that for two ideals (n),(m) of \mathbb{Z} we know that (n)+(m)=R if and only if 1\in (n)+(m) if and only if there exists a,b\in \mathbb{Z} such that an+bm=1. Thus, the ideals (n),(m) are coprime (comaximal) if and only if n,m are coprime in the normal sense. Thus, it makes sense (considering the motivational example of \mathbb{Z}) that perhaps comaximality is a sufficient condition for part c) of the CRT above to be true (i.e. that \phi is surjective). Given finitely many ideals \mathfrak{a}_1,\cdots,\mathfrak{a}_m of an ideal R we say that they are pairwise comaximal if, as the name suggests, the pair \mathfrak{a}_k,\mathfrak{a}_j is comaximal for any i\ne j\in[m]. The most relevant property of comaximal ideals is the following:

\text{ }

Theorem: Let R be a ring and \mathfrak{a},\mathfrak{a}_1,\cdots,\mathfrak{a}_n pairwise comaximal ideals of R. Then, \mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_n=\mathfrak{a}_1\cdots\mathfrak{a}_n and \mathfrak{a}+\mathfrak{a}_1\cdots\mathfrak{a}_n=R.

Proof: We prove the second statement first. The result is true by assumption for n=1, so assume it’s true for \mathfrak{a}_1,\cdots,\mathfrak{a}_n,\mathfrak{a}_{n+1} be any n+1 ideals. By assumption that \mathfrak{a}+\mathfrak{a}_1\cdots\mathfrak{a}_n=R there exists some a\in\mathfrak{a}_1\cdots\mathfrak{a}_n and a'\in\mathfrak{a} such that a'+a=1. We see then that for any a''\in\mathfrak{a}_{n+1} one has that a''=(a'+a)a''=a'a''+aa''\subseteq \mathfrak{a}+\mathfrak{a}_1\cdots\mathfrak{a}_{n+1}. Thus, \mathfrak{a}+\mathfrak{a}_1\cdots\mathfrak{a}_{n+1} contains both \mathfrak{a} and \mathfrak{a}_{n+1} but this implies that \mathfrak{a}+\mathfrak{a}_1\cdots\mathfrak{a}_{n+1}\supseteq \mathfrak{a}+\mathfrak{a}_{n+1}=R from where the conclusion follows.

\text{ }

With this result we now prove that \mathfrak{a}_1\cdots\mathfrak{a}_n=\mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_n.  Once again, we prove this by induction. It’s obviously true for n=1, and so suppose it’s true for n and let \mathfrak{a}_1\cdots\mathfrak{a}_{n+1} are n+1 ideals of R We see then that \mathfrak{a}_1\cdots\mathfrak{a}_{n+1}=\left(\mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_n\right)\mathfrak{a}_{n+1}. Recall that, in general we have the relations (\mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_n)\cap\mathfrak{a}_{n+1}\subseteq (\mathfrak{a}_1\cdots\mathfrak{a}_n)\mathfrak{a}_{n+1} and \left(\mathfrak{a}_1\cdots\mathfrak{a}_n+\mathfrak{a}_{n+1}\right)\left(\mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_n\cap\mathfrak{a}_{n+1}\right)\subseteq\mathfrak{a}_1\cdots\mathfrak{a}_{n+1}. But, by the previous paragraph we have that \mathfrak{a}_1\cdots\mathfrak{a}_n+\mathfrak{a}_{n-1}=R so that this last inclusion becomes \mathfrak{a}_1\cdots\mathfrak{a}_{n+1}\subseteq\mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_{n+1}. The conclusion follows. \blacksquare

\text{ }

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

\text{ }

Theorem (Chinese Remainder Theorem): Let R be a commutative unital ring and \mathfrak{a}_1,\cdots,\mathfrak{a}_n ideals of R. Then, if \phi is the natural map R\to R/\mathfrak{a}_1\times\cdots\times R/\mathfrak{a}_n given by \phi:x\mapsto (x+\mathfrak{a}_1,\cdots,x+\mathfrak{a}_n) is a morphism with \ker\phi=\mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_n. Moreover, \phi is injective if and only if \mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_1=\{0\} and is surjective if and only if \mathfrak{a}_1,\cdots,\mathfrak{a}_n are pairwise comaximal.

Proof: Evidently we have that \phi is a morphism with \ker\phi=\mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_n. From this it immediately follows that \phi is injective if and only \mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_n=\{0\}. The hard part, unfortunately, is the surjectivity condition. So, assume first that \mathfrak{a}_1,\cdots,\mathfrak{a}_n are pairwise comaximal. We know then that \ker\phi=\mathfrak{a}_1\cap\cdots\cap\mathfrak{a}_n=\mathfrak{a}_1\cdots\mathfrak{a}_n. So, with this observation we proceed by induction. For n=1 we are dealing with the canonical epimorphism R\to R/\mathfrak{a}_1 which is trivially surjective. So, suppose the result is true for n and let \mathfrak{a}_1,\cdots,\mathfrak{a}_{n+1} be n+1 ideals of R. Let X=R/\mathfrak{a}_1\times\cdots\times R/\mathfrak{a}_n. By the induction hypothesis and n=1 case we can find, for any (r',s')\in X\times \mathfrak{a}_{n+1} (thinking of r'=(a_1+\mathfrak{a}_1,\cdots,a_n+\mathfrak{a}_{n+1} and s'=a_{n+1}+\mathfrak{a}_{n+1}) there exists a,b\in R such that \phi(r)=(r',\ast) and \phi(s)=(\ast,s'). Since \mathfrak{a}_1\cdots\mathfrak{a}_n+\mathfrak{a}_{n+1}=R there exists x\in \mathfrak{a}_1\cdots\mathfrak{a}_n and y\in\mathfrak{a}_{n+1} such that s-r=x+y. Consider then that since x\in\mathfrak{a}_1\cdots\mathfrak{a}_n and y\in\mathfrak{a}_{n+1} one has that

\text{ }

\begin{aligned}\phi(r+x) &=(r+x+\mathfrak{a}_1,\cdots,r+x+\mathfrak{a}_n,r+x+\mathfrak{a}_{n+1})\\ &=(r+\mathfrak{a}_1,\cdots,r+\mathfrak{a}_n,r+x+y+\mathfrak{a}_{n+1})\\ &=(r+\mathfrak{a}_1,\cdots,r+\mathfrak{a}_n,s+\mathfrak{a}_{n+1})\\ &= (r',s')\end{aligned}

\text{ }

since (r',s') was arbitrary it follows that \phi is surjective and so the induction is complete.

\text{ }

Conversely, suppose that \phi is surjective. Fix two ideals \mathfrak{a}_i,\mathfrak{a}_j. We know there exists some x\in R such that x+\mathfrak{a}_i=1+\mathfrak{a}_i and x+\mathfrak{a}_j=\mathfrak{a}_j. Thus, there exists a_1\in\mathfrak{a}_i and a_2\in\mathfrak{a}_j such that x=1+a_1 and x=a_2 and so a_1-a_2=(x-1)-x=-1 and so \mathfrak{a}_i+\mathfrak{a}_j contains the unit -1 and is thus equal to R. Since i,j was arbitrary the conclusion follows.\blacksquare

\text{ }

Corollary: Let R be a commutative unital ring and \mathfrak{a}_1,\cdots,\mathfrak{a}_n comaximal ideals. Then, R/(\mathfrak{a}_1\cdots\mathfrak{a}_n)\cong R/\mathfrak{a}_1\times\cdots\times R\mathfrak{a}_n.

\text{ }

\text{ }

References:

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

Advertisements

September 6, 2011 - Posted by | Algebra, Ring Theory | , , , , , , ,

8 Comments »

  1. […] 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 | Reply

  2. 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 | Reply

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

  3. […] 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 | Reply

  4. […] 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 | Reply

  5. […] 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 | Reply

  6. […] 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 | Reply

  7. […] 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 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: