Ken Ward's Mathematics Pages

Number Theory Chinese Remainder Theorem due to Gauss

Page Contents

Chinese Remainder Theorem due to Gauss
Example 1
Example 2
Proof of the Chinese Remainder Theorem

The solution is unique modulo M

Chinese Remainder Theorem due to Gauss

We seek to solve the set of equations:
x₁≡r₁ (mod m₁) [1.1.1]
x₂≡r₂ (mod m₂) [1.1.2]
...
x_n≡r_n (mod m_n) [1.1.n]
Where the m's are relatively prime. This is a condition for the use of the formula below (called the Chinese Remainder Theorem) although, as we know, the Chinese Problem might be solvable anyway.

Let M=product of the m's=m₁·m₂...m_n
Let M_i=M/m_i, where i=1...n, that is it is the product of all the m's except m_i.
Also

[1.2]

The formula called the Chinese Remainder Theorem is:

[1.3]

Example 1

A number when divided by 3, gives a remainder 2; when divided by 4, a remainder 3 and when divided by 5, a remainder 4. We seek the number (least positive number).

k	m_k	M_k	Inverse	r_k	r₁M₁inv
1	3	20	2	2	80
2	4	15	3	3	135
3	5	12	3	4	144
					359

Provided the divisors are relatively prime, the formula can be used to find a solution.

M=60
x≡359 (mod 60)
x≡59 (mod 60)
The number is therefore 59.

Example 2

A number when divided by 7, gives a remainder 5; when divided by 9, a remainder 2 and when divided by 11, a remainder 10. We seek the number (least positive number).

k	m_k	M_k	Inverse	r_k	r₁M₁inv	Calculating inverse, s:
1	7	99	1	5	495	99s≡1 (mod 7) s≡1 (mod 7)
2	9	77	2	2	308	77s≡1 (mod 9) 5s≡1 (mod 9) s≡2 (mod 9)
3	11	63	7	10	4410	63s≡1 (mod 11) 8s≡1 (mod 11) s≡7 (mod 11)
					5213

Provided the divisors are relatively prime, the formula can be used to find a solution. The inverses are found, in this case, by testing. Otherwise, Euclid would have to be used.

M=693
x≡5213 (mod 693)
x≡362 (mod 693)

The solution to the equations is 362 (mod 693), which may be verified by trying the remainders.

Proof of the Chinese Remainder Theorem

We seek to solve the set of equations (reproduced from above):
x₁≡r₁ (mod m₁) [1.1.1]
x₂≡r₂ (mod m₂) [1.1.2]
...
x_n≡r_n (mod m_n) [1.1.n]
Where the m's are relatively prime.
Let M=product of the m's=m₁·m₂...m_n
Let M_i=M/m_i, for i=1...n, that is it is the product of all the m's except m_i.
Also

[1.2]

Formulae 1.2 are always solvable, when gcd(M_i, m_i)=1, which they always are when the m's are relatively prime, because gcd(M/m_i, m_i)=1, because M has no factor m_i, and m_i is pair-wise relatively prime with all the other m's.

The formula called the Chinese Remainder Theorem is:

[1.3]
We wish to show that x is a solution to the Equations 1.1.1 to 1.1.n, and that it is unique.

Going back to more basic ideas, we can convert the equations 1.1.1 to 1.1.n to a common modulus, when we can simply add them, by multiplying each equation i, by M_i. For instance, multiplying 1.1.1 by M₁ gives:
M₁x₁≡r₁M₁ (mod M₁·m₁), which gives:
M₁x₁≡r₁M₁ (mod M), because M/m₁·m₁=M

The new equation list becomes, therefore:
M₁x₁≡r₁M₁ (mod M)
M₂x₁≡r₂M₂ (mod M)
...
M_nx_n≡r_nMn (mod M) [4a]

Now multiply each equation (i) by the respective multiplicative inverse of M_i for i=1...n.

[4b]

Now sum all the equations, and equate the right-hand-side to x:

[4.1]

Now we note that in all cases, for i=1 to n, x≡x_i≡r_i (mod m_i), that is, we get the original equations, so x is a solution to the set of equations 1.1.1 to 1.1.n above.

For instance, taking modulo m₁, all the terms will disappear, because they have m₁ as a factor, except M₁, which is relatively prime to m₁. And M1, multiplied by its inverse is 1, modulo m₁, so what remainds is:
x≡r₁ (mod m₁) The corresponding result occurs for all the divisors, m_i.

Therefore, x is a solution to the set of Equations 1.1.1 to 1.1.n.
■

The solution is unique modulo M

Suppose that s is a another solution to the equations, which is unique modulo M, so s and x are distinct.

For each of the equations 1.1.1 to 1.1.n
s≡x≡x_i≡r_i (mod m_i) →
s≡x (mod m_i)
Using a definition of modulus:
s=x+k·m_i
s and x can differ only by a multiple of the modulus, which is zero modulo m_i, so s and x are equaivalent modulo m_i.
■

Number Theory Contents

Ken Ward's Mathematics Pages