Statement:-

If m₁, m₂, .., m_k are pairwise relatively prime positive integers, and if a₁, a₂, .., a_k are any integers, then the simultaneous congruences

x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ a_k (mod m_k) have a solution, and the solution is unique modulo m, where    M = m₁m₂⋅⋅⋅m_k .

 Proof that a solution exists:

To keep the notation simpler, we will assume k = 3.

Note the proof is constructive, i.e., it shows us how to actually construct a solution.

Our simultaneous congruence’s are

x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), x ≡ a₃ (mod m₃)

We have to find integers w₁,w₂,w₃ such that

x = a₁w₁ + a₂w₂ + a₃w₃ .

Moreover, as long as the moduli (m₁, m₂, m₃) remain the same,

 we can use the same w₁, w₂, w₃ with any a₁, a₂, a₃.

 First define: z₁ = M / m₁ = m₂m₃

 z₂ = M / m₂ = m₁m₃

 z₃ = M / m₃ = m₁m₂

 Note that

( i) z₁ ≡ 0 (mod m_j) for j = 2, 3,

( ii) gcd (z₁, m₁) = 1. (If a prime p dividing m₁ also divides z₁= m₂m₃

then p divides m₂, m₃, or )

 and likewise for z₂, z₃.

 Next define:

 y₁ ≡ z₁^–1 (mod m₁)

 y₂ ≡ z₂ ^–1 (mod m₂)

 y₃ ≡ z₃ ^–1 (mod m₃)

 The inverses exist by above, and we can find them by Euclid’s extended algorithm.

 Note that

( iii) y₁z₁ ≡ 0 (mod m_j) for j = 2, 3. (Recall z₁ ≡ 0 (mod mj) )

 (iv) y₁z₁ ≡ 1 (mod m1)

and likewise for y₂z₂, y₃z₃.

Lastly define: w₁ ≡ y₁z₁ (mod M) w₂ ≡ y₂z₂ (mod M) w₃ ≡ y₃z₃ (mod M).

Example 1: Solve the simultaneous congruence’s

x ≡ 2 (mod 7) x ≡ 3 (mod 9)

Solution: Since 7, 9 are pair wise relatively prime, the Chinese Remainder Theorem tells us that there is a unique solution modulo M,

 Where M = 7⋅9 = 63.

We apply the technique of the Chinese Remainder Theorem with k = 2,

 m₁ = 7, m₂ = 9,

a₁ =2, a₂ = 3,

 to obtain the solution. We compute

 z₁ = M / m₁ = m₂   = 9

 z₂ = M / m₂ = m₁  = 7

y₁ ≡ z₁ ^–1 (mod m₁) ≡ 9^–1 (mod 7) ≡ 2^–1 (mod 7) ≡ 4 (mod 7)

y₂ ≡ z₂ ^–1 (mod m₂) ≡ 7^–1 (mod 9) ≡ 7^–1 (mod 9) ≡ 4 (mod 9)

w₁ ≡ y₁z₁ (mod M) ≡ 4⋅9 (mod 63) ≡ 36 (mod 63)

w₂ ≡ y₂z₂ (mod M) ≡ 4⋅7 (mod 63) ≡ 28 (mod 63)

The solution, which is unique modulo 63, is

x ≡ a₁w₁ + a₂w₂ (mod 63)

 ≡ 2⋅36 + 3⋅28 (mod 63)

≡ 156 (mod 63) ≡ 30 (mod 63)

Example 2: Solve the simultaneous congruence’s

x ≡ 6 (mod 7)

 x ≡ 4 (mod 8).

Solution: Since 7, 8 are pair wise relatively prime, the Chinese Remainder Theorem tells us that there is a unique solution modulo M,

 Where M = 7⋅8 = 56.

We apply the technique of the Chinese Remainder Theorem with k = 2,

 m₁ = 7, m₂ = 8,

a₁ =6, a₂ = 4,

 to obtain the solution. We compute

 z₁ = M / m₁ = m₂   = 8

 z₂ = M / m₂ = m₁  = 7

y₁ ≡ z₁ ^–1 (mod m₁) ≡ 8^–1 (mod 7) ≡ 1^–1 (mod 7) ≡ 1 (mod 7)

y₂ ≡ z₂ ^–1 (mod m₂) ≡ 7^–1 (mod 8) ≡ 7^–1 (mod 8) ≡ 7 (mod 9)

w₁ ≡ y₁z₁ (mod M) ≡ 1⋅8 (mod 56) ≡ 8 (mod 56)

w₂ ≡ y₂z₂ (mod M) ≡ 7⋅7 (mod 56) ≡ 49 (mod 56)

The solution, which is unique modulo 63, is

x ≡ a₁w₁ + a₂w₂ (mod 56)

 ≡ 6⋅8 + 4⋅49 (mod 56)

≡ 244 (mod 56) ≡ 20 (mod 56)

Example 3: Solve the simultaneous congruence’s

 x ≡ 6 (mod 11),

x ≡ 13 (mod 16),

 x ≡ 9 (mod 21),

 x ≡ 19 (mod 25).

 Solution: Since 11, 16, 21, and 25 are pairwise relatively prime, the Chinese Remainder Theorem tells us that there is a unique solution modulo M,

 Where M = 11⋅16⋅21⋅25 = 92400.

We apply the technique of the Chinese Remainder Theorem with k = 4,

 m₁ = 11, m₂ = 16, m₃ = 21, m₄ = 25, a₁ = 6, a₂ = 13, a₃ = 9, a₄ = 19,

 to obtain the solution. We compute

 z₁ = M / m₁ = m₂ m₃m₄  = 16⋅21⋅25 = 8400

 z₂ = M / m₂ = m₁ m₃m₄  = 11⋅21⋅25 = 5775

 z₃ = M / m₃ = m₁ m₂m₄= 11⋅16⋅25 = 4400

 z₄ = M / m₄ = m₁ m₂m₃ = 11⋅16⋅21 = 3696

y₁ ≡ z₁ ^–1 (mod m₁) ≡ 8400^–1 (mod 11) ≡ 7^–1 (mod 11) ≡ 8 (mod 11)

y₂ ≡ z₂ ^–1 (mod m₂) ≡ 5775^–1 (mod 16) ≡ 15^–1 (mod 16) ≡ 15 (mod 16)

 y₃ ≡ z₃ ^–1 (mod m₃) ≡ 4400^–1 (mod 21) ≡ 11^–1 (mod 21) ≡ 2 (mod 21)

y₄ ≡ z₄ ^–1 (mod m₄) ≡ 3696^–1 (mod 25) ≡ 21^–1 (mod 25) ≡ 6 (mod 25)

 w₁ ≡ y₁z₁ (mod M) ≡ 8⋅8400 (mod 92400) ≡ 67200 (mod 92400)

w₂ ≡ y₂z₂ (mod M) ≡ 15⋅5775 (mod 92400) ≡ 86625 (mod 92400)

w₃ ≡ y₃z₃ (mod M) ≡ 2⋅4400 (mod 92400) ≡ 8800 (mod 92400)

w₄ ≡ y₄z₄ (mod M) ≡ 6⋅3696 (mod 92400) ≡ 22176 (mod 92400)

The solution, which is unique modulo 92400, is

x ≡ a₁w₁ + a₂w₂ + a₃w₃ + a₄w₄ (mod 92400)

 ≡ 6⋅67200 + 13⋅86625 + 9⋅8800 + 19⋅22176 (mod 92400)

≡ 2029869 (mod 92400) ≡ 89469 (mod 92400)