[PDF] The Chinese Remainder Theorem

101372_6chinese_remainder.pdf

The Chinese Remainder Theorem

Chinese Remainder Theorem: If m 1 , m 2 , .., m k are pairwise relatively prime positive integers, and if a 1 , a 2 , .., a k are any integers, then the simultaneous congruences x a 1 (mod m 1 ), x a 2 (mod m 2 ), ..., x a k (mod m k ) have a solution, and the solution is unique modulo m, where m = m 1 m 2 m k . Proof that a solution exists: To keep the notation simpler, we will assume k = 4. Note the proof is constructive , i.e., it shows us how to actually construct a solution. Our simultaneous congruences are x a 1 (mod m 1 ) , x a 2 (mod m 2 ) , x a 3 (mod m 3 ), x a 4 (mod m 4 ) .

Our goal is to find integers w

1 , w 2 , w 3 , w 4 such that: value mod m 1 value mod m 2 value mod m 3 value mod m 4 w 1 1 0 0 0 w 2 0 1 0 0 w 3 0 0 1 0 w 4 0 0 0 1

Once we have found w

1 , w 2 , w 3 , w 4 , it is easy to construct x: x = a 1 w 1 + a 2 w 2 + a 3 w 3 + a 4 w 4 .

Moreover, as long as the moduli (m

1 , m 2 , m 3 , m 4 ) remain the same, we can use the same w 1 , w 2 , w 3 , w 4 with any a 1 , a 2 , a 3 , a 4 .

First define: z

1 = m / m 1 = m 2 m 3 m 4 z 2 = m / m 2 = m 1 m 3 m 4 z 3 = m / m 3 = m 1 m 2 m 4 z 4 = m / m 4 = m 1 m 2 m 3

Note that

i) z 1 0 (mod m j ) for j = 2, 3, 4. ii) gcd(z 1 ,m 1 ) = 1. (If a prime p dividing m 1 also divides z 1 = m 2 m 3 m 4 , then p divides m 2 , m 3 , or m 4 .) and likewise for z 2 , z 3 , z 4 .

Next define: y

1 z 1-1 (mod m 1 ) y 2 z 2-1 (mod m 2 ) y 3 z 3-1 (mod m 3 ) y 4 z 4-1 (mod m 4 ) The inverses exist by (ii) above, and we can find them by Euclid's extended algorithm. Note that iii) y 1 z 1 0 (mod m j ) for j = 2, 3, 4. (Recall z 1 0 (mod m j ) ) iv) y 1 z 1 1 (mod m 1 ) and likewise for y 2 z 2, y 3 z 3 , y 4 z 4 .

Lastly define: w

1 y 1 z 1 (mod m) w 2 y 2 z 2 (mod m) w 3 y 3 z 3 (mod m) w 4 y 4 z 4 (mod m)

Then w

1 , w 2 , w 3 , and w 4 have the properties in the table on the previous page.

Example: Solve the simultaneous congruences

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 = 11162125 = 92400. We apply the technique of the Chinese Remainder Theorem with k = 4, m 1 = 11, m 2 = 16, m 3 = 21, m 4 = 25, a 1 = 6, a 2 = 13, a 3 = 9, a 4 = 19, to obtain the solution.

We compute

z 1 = m / m 1 = m 2 m 3 m 4 = 162125 = 8400 z 2 = m / m 2 = m 1 m 3 m 4 = 112125 = 5775 z 3 = m / m 3 = m 1 m 2 m 4 = 111625 = 4400 z 4 = m / m 4 = m 1 m 3 m 3 = 111621 = 3696 y 1 z 1-1 (mod m 1 ) 8400 -1 (mod 11) 7 -1 (mod 11) 8 (mod 11) y 2 z 2-1 (mod m 2 ) 5775 -1 (mod 16) 15 -1 (mod 16) 15 (mod 16) y 3 z 3-1 (mod m 3 ) 4400 -1 (mod 21) 11 -1 (mod 21) 2 (mod 21) y 4 z 4-1 (mod m 4 ) 3696 -1 (mod 25) 21 -1 (mod 25) 6 (mod 25) w 1 y 1 z 1 (mod m) 88400 (mod 92400) 67200 (mod 92400) w 2 y 2 z 2 (mod m) 155775 (mod 92400) 86625 (mod 92400) w 3 y 3 z 3 (mod m) 24400 (mod 92400) 8800 (mod 92400) w 4 y 4 z 4 (mod m) 63696 (mod 92400) 22176 (mod 92400)

The solution, which is unique modulo 92400, is

x a 1 w 1 + a 2 w 2 + a 3 w 3 + a 4 w 4 (mod 92400) 667200 + 1386625 + 98800 + 1922176 (mod 92400)
2029869 (mod 92400)
51669 (mod 92400)

Example: Find all solutions of x

2 1 (mod 144).

Solution: 144 = 169 = 2

4 3 2 , and gcd(16,9) = 1. We can replace our congruence by two simultaneous congruences: x 2 1 (mod 16) and x 2 1 (mod 9) x 2 1 (mod 16) has 4 solutions: x 1 or 7 (mod 16) x 2 1 (mod 9) has 2 solutions: x 1 (mod 9)

There are 8 alternatives:

i) x 1 (mod 16) and x 1 (mod 9) ii) x 1 (mod 16) and x -1 (mod 9) iii) x -1 (mod 16) and x 1 (mod 9) iv) x -1 (mod 16) and x -1 (mod 9) v) x 7 (mod 16) and x 1 (mod 9) vi) x 7 (mod 16) and x -1 (mod 9) vii) x -7 (mod 16) and x 1 (mod 9) viii) x -7 (mod 16) and x -1 (mod 9)

By the Chinese Remainder Theorem with k = 2, m

1 = 16 and m 2 = 9, each case above has a unique solution for x modulo 144.

We compute: z

1 = m 2 = 9, z 2 = m 1 = 16, y 1 9 -1 9 (mod 16), y 2 16 -1 4 (mod 9), w 1 99 = 81 (mod 144), w
2 164 64 (mod 144).

The 8 solutions are:

i) x 181 + 164 145 1 (mod 144) ii) x 181 + (-1)64 17 17 (mod 144) iii) x (-1)81 + 164 -17 -17 (mod 144) iv) x (-1)81 + (-1)64 -145 -1 (mod 144) v) x 781 + 164 631 55 (mod 144) vi ) x 781 + (-1)64 503 71 (mod 144) vii) x (-7)81 + 164 -503 -71 (mod 144) viii) x (-7)81 + (-1)64 -603 -55 (mod 144)