nav.gif (1245 bytes)mathematics

Ken Ward's Mathematics Pages

Number Theory Chinese Remainder Theorem due to Gauss

Number Theory Contents

Page Contents

  1. Chinese Remainder Theorem due to Gauss
  2. Example 1
  3. Example 2
  4. Proof of the Chinese Remainder Theorem
    1. The solution is unique modulo M


Chinese Remainder Theorem due to Gauss

We seek to solve the set of equations:
x1≡r1 (mod m1)    [1.1.1]
x2≡r2 (mod m2)    [1.1.2]
...
xn≡rn (mod mn)    [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=m1·m2...mn
Let Mi=M/mi, where i=1...n, that is it is the product of all the m's except mi.
Also
chineseFormula1definition.gif [1.2]
chineseFormula1definition2.gif
The formula called the Chinese Remainder Theorem is:
chineseFormula2.gif [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).
kmkMkInverserkr1*M1*inv
13202280
241533135
351234144
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).
kmkMkInverserkr1*M1*invCalculating inverse, s:
17991549599s≡1 (mod 7)
s≡1 (mod 7)
29772230877s≡1 (mod 9)
5s≡1 (mod 9)
s≡2 (mod 9)
31163710441063s≡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):
x1≡r1 (mod m1)    [1.1.1]
x2≡r2 (mod m2)    [1.1.2]
...
xn≡rn (mod mn)    [1.1.n]
Where the m's are relatively prime.
Let M=product of the m's=m1·m2...mn
Let Mi=M/mi, for i=1...n, that is it is the product of all the m's except mi.
Also
chineseFormula1definition.gif [1.2]
chineseFormula1definition2.gif
Formulae 1.2 are always solvable, when gcd(Mi, mi)=1, which they always are when the m's are relatively prime, because gcd(M/mi, mi)=1, because M has no factor mi, and mi is pair-wise relatively prime with all the other m's.

The formula called the Chinese Remainder Theorem is:
chineseFormula2.gif [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 Mi. For instance, multiplying 1.1.1 by M1 gives:
M1x1≡r1M1 (mod M1·m1), which gives:
M1x1≡r1M1 (mod M), because M/m1·m1=M

The new equation list becomes, therefore:
M1x1≡r1M1 (mod M)
M2x1≡r2M2 (mod M)
...
Mnxn≡rnMn (mod M)      [4a]

Now multiply each equation (i) by the respective multiplicative inverse of Mi for i=1...n.
setOfEquationMI.gif [4b]

Now sum all the equations, and equate the right-hand-side to x:
chineseFormula2MI.gif  [4.1]

Now we note that in all cases, for i=1 to n, x≡xi≡ri (mod mi), 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 m1, all the terms will disappear, because they have m1 as a factor, except M1, which is relatively prime to m1. And M1, multiplied by its inverse is 1, modulo m1, so what remainds is:
x≡r1 (mod m1) The corresponding result occurs for all the divisors, mi.

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≡xi≡ri (mod mi) →
s≡x (mod mi)
Using a definition of modulus:
s=x+k·mi
s and x can differ only by a multiple of the modulus, which is zero modulo mi, so s and x are equaivalent modulo mi.







Number Theory Contents

Ken Ward's Mathematics Pages


Faster Arithmetic - by Ken Ward

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle:
Buy now at Amazon.com
Faster Arithmetic for Adults