# Generalization of the Chinese Remainder Theorem

• Oct 21st 2007, 11: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, 01:07 PM
ThePerfectHacker
Do you mean the following (this is the general Chinese remainder theorem):

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

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