We seek to solve the set of equations: x_{1}≡r_{1} (mod m_{1}) [1.1.1] x_{2}≡r_{2} (mod m_{2}) [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_{1}·m_{2}...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_{1}*M_{1}*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_{1}*M_{1}*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_{1}≡r_{1} (mod m_{1}) [1.1.1] x_{2}≡r_{2} (mod m_{2}) [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_{1}·m_{2}...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_{1} gives: M_{1}x_{1}≡r_{1}M_{1} (mod M_{1}·m_{1}), which gives: M_{1}x_{1}≡r_{1}M_{1} (mod M), because M/m_{1}·m_{1}=M

The new equation list becomes, therefore: M_{1}x_{1}≡r_{1}M_{1} (mod M) M_{2}x_{1}≡r_{2}M_{2} (mod M) ... M_{n}x_{n}≡r_{n}Mn_{} (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_{1}, all the terms will disappear, because they have m_{1} as a factor, except M_{1}, which is relatively prime to m_{1}. And M1, multiplied by its inverse is 1, modulo m_{1}, so what remainds is: x≡r_{1} (mod m_{1}) 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}. ■ _{}

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: