Generalization of the Chinese Remainder Theorem

**the_mannequin** · October 21st 2007, 10:02 AM

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!!

**ThePerfectHacker** · October 21st 2007, 12:07 PM

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.

Thread: Generalization of the Chinese Remainder Theorem

LinkBack

Thread Tools

Display

Generalization of the Chinese Remainder Theorem

Similar Math Help Forum Discussions

The chinese remainder theorem.

Chinese Remainder Theorem

Chinese remainder theorem

CRT(chinese remainder theorem)

Chinese Remainder Theorem

Search Tags