# Generalization of the Chinese Remainder Theorem

• Oct 21st 2007, 10:02 AM
the_mannequin
Generalization of the Chinese Remainder Theorem
Prove the following generalisation of the Chinese Remainder Theorem. Show
that if
m1;m2;m3 are pairwise coprime integers and a1 inZ/m1, a2 inZ/m2,

a
3 inZ/m3 then there is a unique x inZ/(m1m2m3) such that

x =a1 mod m1; x =a2 mod m2; x =a3 mod m3:

Confused!!
• Oct 21st 2007, 12:07 PM
ThePerfectHacker
Do you mean the following (this is the general Chinese remainder theorem):

Let $\displaystyle a_1 \in \mathbb{Z}_{n_1} , a_2 \in \mathbb{Z}_{n_2}, ... , a_k \in \mathbb{Z}_{n_k}$ where $\displaystyle \gcd(n_i,n_j) = 1 \mbox{ for }i\not = j$. Then there exists a unique $\displaystyle x \in \mathbb{Z}_{n_1...n_k}$ so that $\displaystyle x\equiv a_i (\bmod n_i)$ for all $\displaystyle 1\leq i \leq n$.

Here are the steps:
1)Define $\displaystyle n = n_1...n_k$.
2)Define $\displaystyle m_r = n/n_r$, i.e.$\displaystyle m_r = n_1...n_{r-1}n_{r+1}...n_k$.
3)Prove that $\displaystyle \gcd(n_i,m_i) = 1$.
4)Therefore (use #3) the $\displaystyle m_ix = 1$ has unique solution in $\displaystyle \mathbb{Z}_{n_i}$.
5)Denote solution in #4 by $\displaystyle x_i$.
6)Define $\displaystyle \bold{x} = a_1x_im_1 + ... + a_kx_km_k$.
7)Prove that $\displaystyle \bold{x}$ solves $\displaystyle x=a_i$ for each $\displaystyle \mathbb{Z}_{n_i}$.
8)Now prove that there can be no other solution.