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
, ) mod ax b c 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:
, ) , )
, ) , )
1 mod 5 1
4 mod 7 2
x
x

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 1 2 3 4 0
mod 7 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1
By looking at the table we have 11 x = 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 701 x = then this would mean we would have to create a
table with more than 701 columns.
What does the first equation , ) 1 mod 5 x in the above example mean?
Means that 1 5 x k = for some k e . Re-arranging this we have 1 5 x k = +
Similarly the other equation , ) 4 mod 7 x means 4 7 x c = for some c e and
4 7 x c = + . Equating these two equations, 1 5 x k = + and 4 7 x c = + , gives
1 5 4 7
3 7
5
x k c
c
k
= + = +
+
=
Since k is an integer we need 3 7c + to be a multiple of 5. If 1 c = then 3 7 3 7 10 c + = + =
and
10
2
5
k = = .
Substituting these, 1 c = into 4 7 x c = + gives
4 7 4 7 11 x c = + = + =
Putting 2 k = into 1 5 x k = + also yields 11 x = which is our solution from the above
example.
Notes on the Chinese Remainder Theorem 2
Example 2
Solve the simultaneous equations:
, )
, )
31 mod 49
6 mod 20
x
x

Solution
From these equations we have
31 49 31 49
6 20 6 20
x k x k
x c x c
= = +
= = +
where k and c are integers. Equating these last two equations gives
25 49
6 20 31 49
20
k
c k c
+
+ = + =
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 5, 10, 15, k = . Note that 5, 10 k = does not
give a multiple of 20 but 15 does because
, ) 25 49 15
38
20
c
+
= =
Substituting 38 c = into 6 20 x c = + gives , ) 6 20 38 766 x = + = .
Check that this 766 x = satisfies both the given equations:
, )
, )
31 mod 49
6 mod 20
x
x

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:
, )
, )
, )
1 mod 2
1 mod 3
1 mod 5
x
x
x

What does this mean?

Means that
1 2 , 1 3 and 1 5 x k x c x m = = = where k, c and m are integers
This means that 1 x 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 1 x is a multiple of 30 or
1 30 30 1 x n x n = = +
The general solution of the given three equations is 30 1 n + :
, ) , ) 30 1 31, 30 2 1 61, 30 3 1 91, x x x = + = = + = = + =
You may check that each of these solutions satisfies the given equations:
, ) , ) , ) 1 mod 2 , 1 mod 3 , 1 mod 5 x x x
Well under what circumstances do we have a solution to simultaneous congruences?
Notes on the Chinese Remainder Theorem 3
We need to prove the result for general congruences. The proof below is lifted from Burtons
Number Theory book page 79.
Chinese Remainder Theorem.
Let
1 2 3
, , , ,
r
n n n n be positive integers such that
, )
gcd , 1
i j
n n = for i j =
Then the simultaneous linear congruences
, )
, )
, )
1 1
2 2
mod
mod
mod
r r
x a n
x a n
x a n

has a solution satisfying all these equations. Moreover the solution is unique modulo
1 2 3 r
n n n n .
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
1 2 3 r
n n n n n = . For each integer 1, 2, 3, , k r = let
j
1 2 3 1 1
1 2 3 1 1
Cancelling out
k k k r
k k k r k
k k
n n n n n n n n
N n n n n n n n
n n
+
+
= = =


This means that
k
N is the product of all the moduli
i
n with the modulus
k
n missing.
We are given that
, )
gcd , 1
i j
n n = for i j = which implies that
, ) gcd , 1
k k
N n =
Why?
Because by problem 20(a) on page 25 we have:
If , ) , ) gcd , gcd , 1 a b a c = = then , ) gcd , 1 a bc =
Consider the linear congruence
, ) 1 mod
k k
N x n
Does this have any solutions?
Since , ) gcd , 1
k k
N n = the linear congruence
, ) 1 mod
k k
N x n
has a unique solution. Why?
Because by Theorem (4.7) on page 76 we have:
The linear congruence , ) mod ax b n has a solution , ) gcd , g a n = divides b. If
g b then the linear congruence has exactly g solutions.
Let
k
x be the unique solution of , ) 1 mod
k k
N x n which means that
, ) 1 mod
k k k
N x n ()
We construct a solution which satisfies all the given simultaneous linear congruences.
The solution we consider is
1 1 1 2 2 2 3 3 3
'
r r r
x a N x a N x a N x a N x = + + + +
Let us see if this solution ' x satisfies the first given linear congruence:
Notes on the Chinese Remainder Theorem 4
, )
1 1
mod x a n
Taking the solution to modulus
1
n gives
, )
1 1 1 2 2 2 3 3 3 1
' mod
r r r
x a N x a N x a N x a N x n + + + + (*)
By the above definition of
2 3 4
, , , ,
r
N N N N these numbers are multiplies of
1
n .
Therefore
, ) , ) , )
2 2 2 1 3 3 3 1 1
0 mod , 0 mod , , 0 mod
r r r
a N x n a N x n a N x n
Substituting this into (*) we have
, )
1 1 1 1 1 1 1
' 0 0 0 mod x a N x a N x n + + + +
By the above () we have , )
1 1 1
1 mod N x n . Substituting this into the above
, )
1 1 1 1
' mod x a N x n gives
, ) , )
1 1 1 1 1 1
' 1 mod x a N x a a n
Hence ' x satisfies the first simultaneous congruence , )
1 1
mod x a n . 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
, ) ' ' mod
k k
x a y n where 1, 2, 3, , k r =
From this congruence , ) ' ' mod
k
x y n we have
, )
1
' ' n x y , , )
2
' ' n x y , , )
3
' ' n x y , , , ) ' '
r
n x y
Remember we are given that the ns are pairwise prime -
, )
gcd , 1
i j
n n = for i j = .
Applying Corollary 2 on page 23:
If a c and b c with , ) gcd , 1 a b = then ab c .
to the above list gives
, ) , )
1 2 3
' '
r
n n n n x y
This means that
, )
1 2 3
' ' mod
r
x y n n n n
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
1 1 1 2 2 2 3 3 3
'
r r r
x a N x a N x a N x a N x = + + + +
We use this to solve the remaining examples.
Example 4
Solve the following simultaneous linear congruences:
, ) , ) , ) 1 mod 3 , 2 mod 5 , 3 mod 7 x x x
Solution
Using the constructed solution in the proof we have
1 1 1 2 2 2 3 3 3
' x a N x a N x a N x = + + (*)
Each of Ns is given by
k
n
n
where 3 5 7 105 n = = . Hence
Notes on the Chinese Remainder Theorem 5
1 2 3
3 5 7 3 5 7 3 5 7
35, 21 and 15
3 5 7
N N N
/ / /
= = = = = =
/ / /
The as are given to us:
1 2 3
1, 2 and 3 a a a = = =
We need to find the
k
x s which are given by , ) 1 mod
k k k
N x n :
, )
1
35 1 mod 3 x , , )
2
21 1 mod 5 x and , )
3
15 1 mod 7 x
By trial and error we have
1
2 x = ,
2
1 x = and
3
1 x = . Substituting these numbers into (*)
gives
, ) , ) , )
1 1 1 2 2 2 3 3 3
' 1 35 2 2 21 1 3 15 1 157 x a N x a N x a N x = + + = + + =
Hence , ) 157 52 mod 105 . The least positive integer which satisfies the given
congruences is 52 x = . Check that this is correct by substituting into the given linear
congruences.
Example 5
Solve the following simultaneous linear congruences:
, ) , ) , ) 2 1 mod 5 , 3 9 mod 6 , 4 1 mod 7 x x x
Solution
This time we do not have , ) ? mod x m but , ) ? mod ax m . How do we solve these?
We convert them into , ) ? mod x m by multiplying by an appropriate factor. Multiply the
first linear congruence , ) 2 1 mod 5 x by 3 gives
, ) 6 3 mod 5 x x
We can simplify the second , ) 3 9 mod 6 x by dividing by 3 because , ) gcd 3, 6 3 = :
, ) , ) 3 mod 2 1 mod 2 x
We multiply the third , ) 4 1 mod 7 x by 2:
, ) 8 2 mod 7 x x
We solve the equivalent system:
, ) 3 mod 5 x , , ) 1 mod 2 x , , ) 2 mod 7 x
The solution is given by
1 1 1 2 2 2 3 3 3
x a N x a N x a N x = + + (*)
Now using the method described in the proof we have
3 5 7 105 n = =
Hence
1
3 5 7
21
5
N
/
= =
/
2
3 5 7
35
3
N
/
= =
/
3
3 5 7
15
7
N
/
= =
/
The as are
1
3 a = ,
2
1 a = and
3
2 a = .
We need to find the
k
x s which are given by , ) 1 mod
k k k
N x n :
Notes on the Chinese Remainder Theorem 6
, )
1
21 1 mod 5 x , , )
2
35 1 mod 2 x and , )
3
15 1 mod 7 x
The solutions by trial and error are
1
1 x = ,
2
1 x = and
3
1 x = .
Putting all these numbers into (*) gives:
, ) , ) , ) , ) , ) , )
1 1 1 2 2 2 3 3 3
3 21 1 1 35 1 2 15 1 128
x a N x a N x a N x = + +
= + + =
We have , ) 128 23 mod 105 x . The least positive integer is 23 x = . Check this solution
by making sure each of the given congruences is satisfied.
Example 6
Solve the following simultaneous linear congruences:
, ) , ) , ) , ) 2 1 mod 5 , 3 9 mod 6 , 4 1 mod 7 , 5 9 mod 11 x x x x
Solution
This time we do not have , ) ? mod x m but , ) ? mod ax m . How do we solve these?
We convert them into , ) ? mod x m by multiplying by an appropriate factor. Multiply the
first linear congruence , ) 2 1 mod 5 x by 3 gives
, ) 6 3 mod 5 x x
We can simplify the second , ) 3 9 mod 6 x to
, ) , ) 3 mod 2 1 mod 2 x
We multiply the third , ) 4 1 mod 7 x by 2:
, ) 8 2 mod 7 x x
Lastly we multiply the last given congruence , ) 5 9 mod 11 x by 9:
, ) 45 81 4 mod 11 x x
We can rewrite this as , ) 4 mod 11 x .
We solve the equivalent system:
, ) 3 mod 5 x , , ) 1 mod 2 x , , ) 2 mod 7 x and , ) 4 mod 11 x
The solution is given by
1 1 1 2 2 2 3 3 3 4 4 4
x a N x a N x a N x a N x = + + + (*)
Now using the method described in the proof we have
5 2 7 11 770 n = =
Hence
1
2 5 7 11
154
5
N
/
= =
/
2
2 5 7 11
385
2
N
/
= =
/
3
2 5 7 11
110
7
N
/
= =
/
4
2 5 7 11
70
11
N

= =
The as are
1
3 a = ,
2
1 a = ,
3
2 a = and
4
4 a = .
We need to find the
k
x s which are given by , ) 1 mod
k k k
N x n :
Notes on the Chinese Remainder Theorem 7
, )
1
154 1 mod 5 x , , )
2
385 1 mod 2 x , , )
3
110 1 mod 7 x and , )
4
70 1 mod 11 x
The solutions by trial and error are
1
4 x = ,
2
1 x = ,
3
3 x = and
4
3 x = .
Putting all these numbers into (*) gives:
, ) , ) , ) , ) , ) , ) , ) , )
1 1 1 2 2 2 3 3 3 4 4 4
3 154 4 1 385 1 2 110 3 4 70 3 3733
x a N x a N x a N x a N x = + + +
= + + + =
We have , ) 3733 653 mod 770 x . The least positive integer is 653 x = .
Check that this solution is correct.
Summary
For simultaneous linear congruences we can apply the Chinese Remainder Theorem to
resolve for the unknown.