Chinese Remainder Theorem 5g4720

Notes on the Chinese Remainder Theorem

1

Chapter 4: Congruences Chinese Remainder Theorem By the end of this section you will be able to  prove the Chinese Remainder Theorem  apply this theorem to solve simultaneous linear congruences Up to now we have solved a single linear congruence such as ax  b  c  mod n  In this section we examine solving a set of simultaneous linear equations. How do we solve these? First we look at an example and then develop a general method. Example 1 Find the value of x which satisfies both the following equations: x  1  mod 5  1 x  4  mod 7 

 2

Solution We need to find a value of x such that equations (1) and (2) are true. Let us first use brute force to resolve these equations. Creating a table of values: x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 mod 5 1 2 3 4 0 1 2 3 4 0 2 3 4 0 1 mod 7 1 2 3 4 5 6 0 1 2 3 5 6 0 1 4 By looking at the table we have x  11 will satisfy both the above equations (1) and (2) because 11  1  mod 5  , 11  4  mod 7  Of course we can apply brute force for simple integer values. However we need a systematic approach to solve these because x may be a large number and we just do not have the time to create a table for large x. Say if x  701 then this would mean we would have to create a table with more than 701 columns. What does the first equation x  1  mod 5  in the above example mean? Means that x  1  5k for some k   . Re-arranging this we have x  1  5k Similarly the other equation x  4  mod 7  means x  4  7c for some c   and x  4  7c . Equating these two equations, x  1  5k and x  4  7c , gives x  1  5k  4  7c

3  7c 5 Since k is an integer we need 3  7c to be a multiple of 5. If c  1 then 3  7c  3  7  10 10 and k  2. 5 Substituting these, c  1 into x  4  7c gives x  4  7c  4  7  11 Putting k  2 into x  1  5k also yields x  11 which is our solution from the above example. k

Notes on the Chinese Remainder Theorem Example 2 Solve the simultaneous equations: x  31  mod 49  x  6  mod 20 

Solution From these equations we have

x  31  49k  x  31  49k

x  6  20c  x  6  20c where k and c are integers. Equating these last two equations gives 25  49k 6  20c  31  49k  c  20 Since we want integer solutions so we try values of k such that the numerator 25  49k is a multiple of 20. Hence we trial multiples of 5 for k, that is k  5, 10, 15,  . Note that k  5, 10 does not give a multiple of 20 but 15 does because 25  49 15  c  38 20 Substituting c  38 into x  6  20c gives x  6  20  38   766 .

Check that this x  766 satisfies both the given equations: x  31  mod 49  x  6  mod 20 

Example 3 Find an integer x such that when divided by 2, 3 and 5 the remainder is 1. Solution We can write these as congruences: x  1  mod 2 

x  1  mod 3 x  1  mod 5  What does this mean? Means that x  1  2k , x  1  3c and x  1  5m where k, c and m are integers This means that x  1 is a multiple of 2, 3 and 5. Which number is a multiple of 2, 3 and 5? Since gcd  2, 3, 5   1 so the smallest number which is a multiple of 2, 3 and 5 is 2  3  5  30 This means that x  1 is a multiple of 30 or x  1  30n  x  30n  1 The general solution of the given three equations is 30n  1 : x  30  1  31, x   30  2   1  61, x   30  3  1  91,  You may check that each of these solutions satisfies the given equations: x  1  mod 2  , x  1  mod 3 , x  1  mod 5  Well under what circumstances do we have a solution to simultaneous congruences?

2

Notes on the Chinese Remainder Theorem

3

We need to prove the result for general congruences. The proof below is lifted from Burton’s Number Theory book page 79. Chinese Remainder Theorem. Let n1 , n2 , n3 ,  , nr be positive integers such that gcd  ni , n j   1 for i  j

Then the simultaneous linear congruences x  a1  mod n1 

x  a2  mod n2  

x  ar  mod nr  has a solution satisfying all these equations. Moreover the solution is unique modulo n1n2 n3  nr . How do we prove this result? We need to prove two things – (1) existence of solution and (2) uniqueness of solution Proof. (1) Existence Let n  n1n2 n3  nr . For each integer k  1, 2, 3,  , r let n n1n2 n3  nk 1nk nk 1  nr Nk    n1n2 n3  nk 1nk 1  nr Cancelling out nk  nk nk This means that N k is the product of all the moduli ni with the modulus nk missing. We are given that gcd  ni , n j   1 for i  j which implies that

gcd  N k , nk   1 Why? Because by problem 20(a) on page 25 we have: If gcd  a, b   gcd  a, c   1 then gcd  a, bc   1 Consider the linear congruence

N k x  1  mod nk 

Does this have any solutions? Since gcd  N k , nk   1 the linear congruence

N k x  1  mod nk 

has a unique solution. Why? Because by Theorem (4.7) on page 76 we have: The linear congruence ax  b  mod n  has a solution  g  gcd  a, n  divides b. If

g b then the linear congruence has exactly g solutions. Let xk be the unique solution of N k x  1  mod nk  which means that

N k xk  1  mod nk  (†) We construct a solution which satisfies all the given simultaneous linear congruences. The solution we consider is x '  a1 N1 x1  a2 N 2 x2  a3 N 3 x3    ar N r xr Let us see if this solution x ' satisfies the first given linear congruence:

Notes on the Chinese Remainder Theorem

4

x  a1  mod n1  Taking the solution to modulus n1 gives

x '  a1 N1 x1  a2 N 2 x2  a3 N 3 x3    ar N r xr

 mod

n1 

(*)

By the above definition of N 2 , N 3 , N 4 ,  , N r these numbers are multiplies of n1 . Therefore a2 N 2 x2  0  mod n1  , a3 N 3 x3  0  mod n1  , , ar N r xr  0  mod n1  Substituting this into (*) we have x '  a1 N1 x1  0  0    0  a1 N1 x1  mod n1  By the above (†) we have N1 x1  1  mod n1  . Substituting this into the above

x '  a1 N1 x1  mod n1  gives

x '  a1 N1 x1  a1 1  a1  mod n1 

Hence x ' satisfies the first simultaneous congruence x  a1  mod n1  . Similarly we can show that the solution constructed satisfies the remaining congruences. (2) Uniqueness Suppose there is another solution y ' which satisfies the given linear congruences. This means we have x '  ak  y '  mod nk  where k  1, 2, 3,  , r From this congruence x '  y '  mod nk  we have

n1

 x ' y ' ,

n2

 x ' y ' ,

n3

 x ' y ' ,

 , nr

 x ' y '

we are given that the n’s are pairwise prime - gcd  ni , n j   1 for i  j . Applying Corollary 2 on page 23: If a c and b c with gcd  a, b   1 then ab c . to the above list gives

 n1n2 n3  nr   x ' y '

This means that

x '  y '  mod n1n2 n3  nr This completes our proof.



■ The proof gives us a systematic approach on how to construct the solution of any given linear simultaneous congruences. In the proof the solution was x '  a1 N1 x1  a2 N 2 x2  a3 N 3 x3    ar N r xr We use this to solve the remaining examples. Example 4 Solve the following simultaneous linear congruences: x  1  mod 3 , x  2  mod 5  , x  3  mod 7  Solution Using the constructed solution in the proof we have x '  a1 N1 x1  a2 N 2 x2  a3 N 3 x3 (*) n Each of N’s is given by where n  3  5  7  105 . Hence nk

Notes on the Chinese Remainder Theorem

5

3  5  7 3  5  7 3  5  7  35, N 2   21 and N 3   15 3 5 7 The a’s are given to us: a1  1, a2  2 and a3  3 N1 

We need to find the xk ’s which are given by N k xk  1  mod nk  :

35 x1  1  mod 3 , 21x2  1  mod 5  and 15 x3  1  mod 7 

By trial and error we have x1  2 , x2  1 and x3  1 . Substituting these numbers into (*) gives x '  a1 N1 x1  a2 N 2 x2  a3 N 3 x3  1 35  2    2  21 1   3  15  1  157 Hence 157  52  mod 105  . The least positive integer which satisfies the given

congruences is x  52 . Check that this is correct by substituting into the given linear congruences. Example 5 Solve the following simultaneous linear congruences: 2 x  1  mod 5  , 3 x  9  mod 6  , 4 x  1  mod 7  Solution This time we do not have x  ?  mod m  but ax  ?  mod m  . How do we solve these? We convert them into x  ?  mod m  by multiplying by an appropriate factor. Multiply the first linear congruence 2 x  1  mod 5  by 3 gives

6 x  x  3  mod 5  We can simplify the second 3x  9  mod 6  by dividing by 3 because gcd  3, 6   3 :

x  3  mod 2   1  mod 2  We multiply the third 4 x  1  mod 7  by 2:

8 x  x  2  mod 7  We solve the equivalent system: x  3  mod 5  , x  1  mod 2  , x  2  mod 7  The solution is given by x  a1 N1 x1  a2 N 2 x2  a3 N 3 x3 (*) Now using the method described in the proof we have n  3  5  7  105 Hence 3  5  7 N1   21 5 3  5  7 N2   35 3 3  5  7 N3   15 7 The a’s are a1  3 , a2  1 and a3  2 . We need to find the xk ’s which are given by N k xk  1  mod nk  :

Notes on the Chinese Remainder Theorem

6

21x1  1  mod 5  , 35 x2  1  mod 2  and 15 x3  1  mod 7  The solutions by trial and error are x1  1 , x2  1 and x3  1 . Putting all these numbers into (*) gives: x  a1 N1 x1  a2 N 2 x2  a3 N 3 x3

 3  211  1 35 1  2 15 1  128

We have x  128  23  mod 105  . The least positive integer is x  23 . Check this solution by making sure each of the given congruences is satisfied. Example 6 Solve the following simultaneous linear congruences: 2 x  1  mod 5  , 3x  9  mod 6  , 4 x  1  mod 7  , 5 x  9  mod 11 Solution This time we do not have x  ?  mod m  but ax  ?  mod m  . How do we solve these? We convert them into x  ?  mod m  by multiplying by an appropriate factor. Multiply the first linear congruence 2 x  1  mod 5  by 3 gives

6 x  x  3  mod 5  We can simplify the second 3x  9  mod 6  to

x  3  mod 2   1  mod 2  We multiply the third 4 x  1  mod 7  by 2:

8 x  x  2  mod 7  Lastly we multiply the last given congruence 5 x  9  mod 11 by 9:

45 x  x  81  4  mod 11 We can rewrite this as x  4  mod 11 . We solve the equivalent system: x  3  mod 5  , x  1  mod 2  , x  2  mod 7  and x  4  mod 11 The solution is given by x  a1 N1 x1  a2 N 2 x2  a3 N 3 x3  a4 N 4 x4 (*) Now using the method described in the proof we have n  5  2  7  11  770 Hence 2  5  7  11 N1   154 5 2  5  7  11 N2   385 2 2  5  7  11 N3   110 7 2  5  7  11 N4   70 11 The a’s are a1  3 , a2  1 , a3  2 and a4  4 . We need to find the xk ’s which are given by N k xk  1  mod nk  :

Notes on the Chinese Remainder Theorem

154 x1  1  mod 5  , 385 x2  1  mod 2  , 110 x3  1  mod 7  and 70 x4  1  mod 11 The solutions by trial and error are x1  4 , x2  1 , x3  3 and x4  3 . Putting all these numbers into (*) gives: x  a1 N1 x1  a2 N 2 x2  a3 N 3 x3  a4 N 4 x4

 3 154  4   1 385 1  2 110  3  4  70  3  3733

We have x  3733  653  mod 770  . The least positive integer is x  653 . Check that this solution is correct. Summary For simultaneous linear congruences we can apply the Chinese Remainder Theorem to resolve for the unknown.

7