Chinese Remainder Theorem Interpretation

Could someone comment on my interpreatation of this theorem. My thoughts are mainly in the last piece from "we now justify...". Thank you in advance.

Lemma 1 Let $x,y,z,d\in\mathbb{Z}$.

i) $x\equiv x \ \mathrm{mod}(d)$

ii) $(x\equiv y \ \mathrm{mod}(d) \ \wedge \ y\equiv z \ \mathrm{mod}(d)) \ \Rightarrow \ x\equiv z \ \mathrm{mod}(d)$

$i)$ Since $d|(x-x)$ it follows immediately from the definition of congruences. $ii)$ It follows from the premise that $\dfrac{(x-y)-(y-z)}{d} = \dfrac{x-z}{d}$, and hence $x\equiv z \ \mathrm{mod}(d)$.

Corrollary 1 If $a$ and $b$ are relatively prime, and $a$ and $c$ are relatively prime then $a$ and $a$ and $bc$ are relatively prime.

[Chinese Remainder Theorem] Suppose that $N=n_{1}\cdots n_{t}$, where $n_{1},\ldots,n_{t}\in\mathbb{Z}\setminus{\{0\}}$ and $\gcd(n_{i},n_{j})=1$ for $i\neq j$. Consider the system

\begin{equation} \begin{aligned} X&\equiv a_1 \ \mathrm{mod}(n_1)\\ X&\equiv a_2 \ \mathrm{mod}(n_2)\\ &\hspace{5.5pt}\vdots\\ X&\equiv a_t \ \mathrm{mod}(n_t) \end{aligned} \end{equation} of congruences for $a_{1},\ldots,a_{t}\in\mathbb{Z}$. Then the system has a solution $X\in\mathbb{Z}$.

By repeated application of Corrolary 1 we see that $n_{j}$ and $N/{n_{j}}$ are relatively prime. From the Extended Euclidean algorithm we can find integers $\lambda_{j}$ and $\mu_{j}$ such that \begin{align*} \lambda_{1}n_{1} + \mu_{1}N/n_{1} &= 1\\ \lambda_{2}n_{2} + \mu_{2}N/n_{2} &= 1\\ &\hspace{5.5pt}\vdots\\ \lambda_{t}n_{t} + \mu_{t}N/n_{t} &= 1. \end{align*} Let $A_{j}=\mu_{j}N/n_{j}$ for $j=1,\ldots,t$. Notice that $A_{j}\equiv 1\ \mathrm{mod}(n_j)$ which is equivalent to $n_{j}|(1-\lambda_{j}n_{j}-1)$ which holds. We also notice that ${A_{j}\equiv 0\ \mathrm{mod}(n_i)}$ if $i\neq j$, which is true because $n_{i}\in A_{j}$. We now build a solution to the system with these informations by putting \begin{align} X = a_{1}A_{1}+\cdots + a_{t}A_{t}. \end{align} We now jusity the solution. First notice that $a_{1}\equiv a_{1} \ \mathrm{mod}(n_{1})$ by Lemma 1. Since $A_{1}\equiv 1\ \mathrm{mod}(n_1)$ we have $a_{1}A_{j}\equiv a_{1}\ \mathrm{mod}(n_1)$. So clearly $a_{1}A_{j}$ is a solution to $X\equiv a_1 \ \mathrm{mod}(n_1)$ Now we let \begin{align} {a_{1}A_{1}+\cdots + a_{t}A_{t}\equiv a_1 \ \mathrm{mod}(n_1)}, \end{align} which imply that \begin{align*} n_{1}&|(a_{1}A_{1}+\cdots + a_{t}A_{t}-a_{1})\\ n_{1}&|(a_{1}(A_{1}-1)+\cdots + a_{t}A_{t})\\ n_{1}&|(-a_{1}(1-A_{1})+\cdots + a_{t}A_{t})\\ n_{1}&|(-a_{1}(\lambda_{1}n_{1})+\cdots + a_{t}A_{t}).\\ \end{align*} Thus $a_{1}A_{1}+\cdots + a_{t}A_{t}$ is also a solution to $X\equiv a_1 \ \mathrm{mod}(n_1)$. In a similar way, or by induction, it could be shown that $a_{1}A_{1}+\cdots + a_{t}A_{t}$ is a solution to all the equations in the system.

• By "comment on my interpretation" do you mean "comment on my proof"? Those two things seem completely different, to me anyhow. – rschwieb Aug 26 '13 at 14:31

You are essentially correct. A few small typos/quibbles.

In the paragraph starting with "We now justify the solution", the congruence should read $a_1A_1 \equiv a_1 (\operatorname{mod} n_1)$. One might also want to remark here that $a_1A_1 \equiv 0 (\operatorname{mod} n_j)$ for all $j \neq 1$.

At the end of this paragraph you say "Now we let". At this point in the proof, you can't "let" anything. $a_i$, $A_i$, and $n_i$ are all chosen. You certainly have this equation. It is justified by the previous paragraph (if you add in my suggestion above), so I think the next four lines of displayed equations are unnecessary.

Finally, it may very well be possible to prove this by induction. However, the way you've set up this proof it really doesn't extend to an inductive argument. "In a similar way" is perfectly fine.

No matter what ring $R$ you're given and set of ideal $\{I_j\mid i\in 1,\dots n\}$ there is always a ring homomorphism $f:R\to \prod_j R/I_j$ given by $r\mapsto (r+I_1,r+I_2,\dots,r+I_n)$. The thing is that this mapping does not have to be very nice, and in particular it doesn't have to be surjective.

The interpretation of the Chinese Remainder Theorem that's stuck with me the longest is that when the $I_j$ are pairwise coprime $f$ is surjective. That means "you can hit anything in the product ring with something from $R$". Let's see why that helps us with the version of the Chinese remainder theorem you're talking about.

Translating what you wrote above, we are interested in $R=\Bbb Z$ and the ideals $I_j=(n_i)\lhd \Bbb Z$. We are establishing that there always exists $z\in \Bbb Z$ mapping to $(a_1 + I_1,\dots,a_n+ I_n)\in\prod_{j=1}^n \Bbb Z/I_j$ no matter which $a_j$ we want.

Once we have found this $z$ such that $(z+I_1,\dots,z+I_n)=(a_1 + I_1,\dots,a_n+ I_n)$, the definition of equality in the product ring says that $z+I_j=a_j+I_j$ for all $j$, and again by definition this means $z-a_j\in I_j$ for all $j$. Recalling that $I_j=(n_j)$, we finally see that this just means exactly $z\equiv a_j\pmod{n_j}$ for all $j$.

If the ideals had not been pairwise coprime, then there might be targets $)=(a_1 + I_1,\dots,a_n+ I_n)$ that are impossible to hit, and there might not be a solution. But the CRT assures us there is one.

I think most proofs I've seen, including the one you have written out, essentially construct a solution by doing this:

• First construct $z_j$ such that $z_j\mapsto (0,\dots,1\dots,0)$ where $1$ is in the $j$'th position.
• Then see that $\sum a_jz_j$ maps to $(a_1 + I_1,\dots,a_n+ I_n)$
• Rejoice (as Mariano is sometimes known to say)
• I'm new to algebra, so I it's greek to me the most of it. In fact, the semester hasn't startet yet. I'm just ahead. – New_to_this Aug 26 '13 at 13:36
• Dear @New_to_this OK: yeah, I wouldn't be surprised if this isn't what you were looking for. When your question asked for comments on interpretation of the theorem, I answered accordingly. I wasn't thinking about commenting on the quality of your proof. – rschwieb Aug 26 '13 at 14:32
• I wrote my interpretation of... :). Thank you anyway. I may look back on this, when I've studied a lot more algebra. Have a nice day. – New_to_this Aug 26 '13 at 14:46