  # Ken Ward's Mathematics Pages

## Number Theory Chinese Remainder Theorem due to Gauss

Number Theory Contents

## 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 [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 mk Mk Inverse rk r1*M1*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 mk Mk Inverse rk r1*M1*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):
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 [1.2] 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: [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. [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≡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 remains 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: 