Chinese Remainder Theorem - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

 Page 1


THE CHINESE REMAINDER THEOREM
1. Introduction
The Chinese remainder theorem says we can uniquely solve any pair of congruences that
have relatively prime moduli.
Theorem 1.1. Let m and n be relatively prime positive integers. For any integers a and
b, the pair of congruences
xa modm; xb modn
has a solution, and this solution is uniquely determined modulo mn.
What is important here is that m and n are relatively prime. There are no constraints
at all on a and b.
Example 1.2. The congruences x 6 mod 9 and x 4 mod 11 hold when x = 15, and
more generally when x 15 mod 99, and they do not hold for any other x. The modulus
99 is 9
 11.
We will prove the Chinese remainder theorem, including a version for more than two
moduli, and see some ways it is applied to count solutions of congruences.
2. A proof of the Chinese remainder theorem
Proof. First we show there is always a solution. Then we will show it is unique modulo mn.
Existence of Solution. To show that the simultaneous congruences
xa modm; xb modn
have a common solution in Z, we give two proofs.
First proof: Write the rst congruence as an equation in Z, say x = a +my for some
y2Z. Then the second congruence is the same as
a +myb modn:
Subtracting a from both sides, we need to solve for y in
(2.1) myba modn:
Since (m;n) = 1, we know m modn is invertible. Let m
0
be an inverse for m modn,
so mm
0
 1 modn. Multiplying through (2.1) by m
0
, we have y m
0
(ba) modn, so
ym
0
(ba) +nz where z2Z. Then
x =a +my =a +m(m
0
(ba) +nz) =a +mm
0
(ba) +mnz:
1
Page 2


THE CHINESE REMAINDER THEOREM
1. Introduction
The Chinese remainder theorem says we can uniquely solve any pair of congruences that
have relatively prime moduli.
Theorem 1.1. Let m and n be relatively prime positive integers. For any integers a and
b, the pair of congruences
xa modm; xb modn
has a solution, and this solution is uniquely determined modulo mn.
What is important here is that m and n are relatively prime. There are no constraints
at all on a and b.
Example 1.2. The congruences x 6 mod 9 and x 4 mod 11 hold when x = 15, and
more generally when x 15 mod 99, and they do not hold for any other x. The modulus
99 is 9
 11.
We will prove the Chinese remainder theorem, including a version for more than two
moduli, and see some ways it is applied to count solutions of congruences.
2. A proof of the Chinese remainder theorem
Proof. First we show there is always a solution. Then we will show it is unique modulo mn.
Existence of Solution. To show that the simultaneous congruences
xa modm; xb modn
have a common solution in Z, we give two proofs.
First proof: Write the rst congruence as an equation in Z, say x = a +my for some
y2Z. Then the second congruence is the same as
a +myb modn:
Subtracting a from both sides, we need to solve for y in
(2.1) myba modn:
Since (m;n) = 1, we know m modn is invertible. Let m
0
be an inverse for m modn,
so mm
0
 1 modn. Multiplying through (2.1) by m
0
, we have y m
0
(ba) modn, so
ym
0
(ba) +nz where z2Z. Then
x =a +my =a +m(m
0
(ba) +nz) =a +mm
0
(ba) +mnz:
1
So if x satises the original two congruences it must have this form. Let's now check this
expression, for every z2Z, really satises the original two congruences:
a +mm
0
(ba) +mnza + 0 + 0a modm
and
a +mm
0
(ba) +mnza + 1(ba) + 0b modn:
Second proof: Write both congruences as equations in Z: x = a +my and x = b +nz
for integers y and z that need to be determined. (Why would it be a bad idea to write
x = a +my and x = b +ny?) The integers of the form a +my are the numbers that
are congruent to a modm, and the integers of the form b +nz are the numbers that are
congruent to b modn. Finding a common solution to the two congruences amounts to
nding y and z in Z such that
a +my =b +nz;
which is the same as
(2.2) mynz =ba:
Can we nd such y and z for any a, b, m, and n where (m;n) = 1? Bezout's identity tells
us 1 is aZ-linear combination ofm andn, and therefore any integer isZ-linear combination
of m and n (why?). Therefore integers y and z satisfying (2.2) exist.
Uniqueness of Solution. If x =c and x =c
0
both satisfy
xa modm; xb modn;
then we have c c
0
modm and c c
0
modn. Then mj (cc
0
) and nj (cc
0
). Since
(m;n) = 1, the product mn divides cc
0
, which means c c
0
modmn. This shows any
two solutions to the initial pair of congruences are the same modulo mn. 
3. Extension to more than two congruences
The Chinese remainder theorem can be extended from two congruences to any nite
number of congruences, but we have to be careful about the way in which the moduli are
relatively prime. Consider the three congruences
x 1 mod 6; x 4 mod 10; x 7 mod 15:
While there is no common factor of 6, 10, and 15 greater than 1, these congruences do not
admit a common solution: any solution to the rst congruence is odd, while any solution
to the second congruence is even. When we have more than two moduli, we have to be
sensitive to the dierence between saying numbers are collectively relatively prime (no
common factor greater than 1 divides them all) and pairwise relatively prime (no common
factor greater than 1 divides any two of the numbers). For instance, 6, 10, and 15 are
collectively relatively prime but not pairwise relatively prime. Here is a more general form
of the Chinese remainder theorem.
Theorem 3.1. For r 2, let m
1
;m
2
;:::;m
r
be nonzero integers that are pairwise rela-
tively prime: (m
i
;m
j
) = 1 for i6= j. Then, for any integers a
1
;a
2
;:::;a
r
, the system of
congruences
xa
1
modm
1
; xa
2
modm
2
; :::; xa
r
modm
r
;
has a solution, and this solution is uniquely determined modulo m
1
m
2



m
r
.
Example3.2. The congruencesx 1 mod 3,x 2 mod 5,x 2 mod 7 are satised when
x = 37, more generally for any x 37 mod 105 and for no other x. Note 105 = 3
 5
 7.
Page 3


THE CHINESE REMAINDER THEOREM
1. Introduction
The Chinese remainder theorem says we can uniquely solve any pair of congruences that
have relatively prime moduli.
Theorem 1.1. Let m and n be relatively prime positive integers. For any integers a and
b, the pair of congruences
xa modm; xb modn
has a solution, and this solution is uniquely determined modulo mn.
What is important here is that m and n are relatively prime. There are no constraints
at all on a and b.
Example 1.2. The congruences x 6 mod 9 and x 4 mod 11 hold when x = 15, and
more generally when x 15 mod 99, and they do not hold for any other x. The modulus
99 is 9
 11.
We will prove the Chinese remainder theorem, including a version for more than two
moduli, and see some ways it is applied to count solutions of congruences.
2. A proof of the Chinese remainder theorem
Proof. First we show there is always a solution. Then we will show it is unique modulo mn.
Existence of Solution. To show that the simultaneous congruences
xa modm; xb modn
have a common solution in Z, we give two proofs.
First proof: Write the rst congruence as an equation in Z, say x = a +my for some
y2Z. Then the second congruence is the same as
a +myb modn:
Subtracting a from both sides, we need to solve for y in
(2.1) myba modn:
Since (m;n) = 1, we know m modn is invertible. Let m
0
be an inverse for m modn,
so mm
0
 1 modn. Multiplying through (2.1) by m
0
, we have y m
0
(ba) modn, so
ym
0
(ba) +nz where z2Z. Then
x =a +my =a +m(m
0
(ba) +nz) =a +mm
0
(ba) +mnz:
1
So if x satises the original two congruences it must have this form. Let's now check this
expression, for every z2Z, really satises the original two congruences:
a +mm
0
(ba) +mnza + 0 + 0a modm
and
a +mm
0
(ba) +mnza + 1(ba) + 0b modn:
Second proof: Write both congruences as equations in Z: x = a +my and x = b +nz
for integers y and z that need to be determined. (Why would it be a bad idea to write
x = a +my and x = b +ny?) The integers of the form a +my are the numbers that
are congruent to a modm, and the integers of the form b +nz are the numbers that are
congruent to b modn. Finding a common solution to the two congruences amounts to
nding y and z in Z such that
a +my =b +nz;
which is the same as
(2.2) mynz =ba:
Can we nd such y and z for any a, b, m, and n where (m;n) = 1? Bezout's identity tells
us 1 is aZ-linear combination ofm andn, and therefore any integer isZ-linear combination
of m and n (why?). Therefore integers y and z satisfying (2.2) exist.
Uniqueness of Solution. If x =c and x =c
0
both satisfy
xa modm; xb modn;
then we have c c
0
modm and c c
0
modn. Then mj (cc
0
) and nj (cc
0
). Since
(m;n) = 1, the product mn divides cc
0
, which means c c
0
modmn. This shows any
two solutions to the initial pair of congruences are the same modulo mn. 
3. Extension to more than two congruences
The Chinese remainder theorem can be extended from two congruences to any nite
number of congruences, but we have to be careful about the way in which the moduli are
relatively prime. Consider the three congruences
x 1 mod 6; x 4 mod 10; x 7 mod 15:
While there is no common factor of 6, 10, and 15 greater than 1, these congruences do not
admit a common solution: any solution to the rst congruence is odd, while any solution
to the second congruence is even. When we have more than two moduli, we have to be
sensitive to the dierence between saying numbers are collectively relatively prime (no
common factor greater than 1 divides them all) and pairwise relatively prime (no common
factor greater than 1 divides any two of the numbers). For instance, 6, 10, and 15 are
collectively relatively prime but not pairwise relatively prime. Here is a more general form
of the Chinese remainder theorem.
Theorem 3.1. For r 2, let m
1
;m
2
;:::;m
r
be nonzero integers that are pairwise rela-
tively prime: (m
i
;m
j
) = 1 for i6= j. Then, for any integers a
1
;a
2
;:::;a
r
, the system of
congruences
xa
1
modm
1
; xa
2
modm
2
; :::; xa
r
modm
r
;
has a solution, and this solution is uniquely determined modulo m
1
m
2



m
r
.
Example3.2. The congruencesx 1 mod 3,x 2 mod 5,x 2 mod 7 are satised when
x = 37, more generally for any x 37 mod 105 and for no other x. Note 105 = 3
 5
 7.
Proof. First we show there is always a solution. Then we will show it is unique modulo
m
1
m
2



m
r
.
Existence of Solution. We argue by induction on r. The base case r = 2 is Theorem
1.1, which has been proved already.
Now we pass to the inductive step. Suppose all simultaneous congruences with r pairwise
relatively prime moduli can be solved. Consider a system of simultaneous congruences with
r + 1 pairwise relatively prime moduli:
xa
1
modm
1
; :::; xa
r
modm
r
; xa
r+1
modm
r+1
;
where (m
i
;m
j
) = 1 for all i6= j and the a
i
's are arbitrary. By the inductive hypothesis,
there is a solution b to the rst r congruences, say
ba
1
modm
1
; ba
2
modm
2
; :::; ba
r
modm
r
:
Now consider the system of two congruences
(3.1) xb modm
1
m
2



m
r
; xa
r+1
modm
r+1
:
Since (m
i
;m
r+1
) = 1 fori = 1; 2;:::;r, we have (m
1
m
2



m
r
;m
r+1
) = 1, so the two moduli
in (3.1) are relatively prime. Then by the case of two congruences, namely Theorem 1.1,
there is a solution to (3.1). Call it c. Since cb modm
1
m
2



m
r
, we have cb modm
i
for i = 1; 2;:::;r. From the choice of b we have ba
i
modm
i
for i = 1; 2;:::;r. Therefore
c a
i
modm
i
for i = 1; 2;:::;r. Also, c a
r+1
modm
r+1
from the choice of c, so we see
c satises the r + 1 given congruences.
This concludes the inductive step, so a solution exists.
Uniqueness of Solution. If x =c and x =c
0
both satisfy
xa
1
modm
1
; xa
2
modm
2
; :::; xa
r
modm
r
;
then we have c c
0
modm
i
for i = 1; 2;:::;r, so m
i
j (cc
0
) for i = 1; 2;:::;r. Since the
m
i
's are pairwise relatively prime, their product m
1
m
2



m
r
divides cc
0
, which means
cc
0
modm
1
m
2



m
r
. This shows any two solutions to the given system of congruences
are the same when viewed modulo m
1
m
2



m
r
. 
4. Applications
The signicance of the Chinese remainder theorem is that it often reduces a question
about modulusmn, where (m;n) = 1, to the same question for modulusm andn separately.
In this way, questions about modular arithmetic can often be reduced to the special case of
prime power moduli. We will see how this works for several counting problems, often using
two features of modular arithmetic with two moduli:
 if djm it makes sense to reduce integers mod m to integers mod d: if xy modm
then x y modd. For example, if x y mod 10 then x y mod 5 since if xy
is divisible by 10 then it is also divisible by 5. (In contrast, it makes no sense to
reduce x mod 10 to x mod 3, since there are congruent numbers mod 10 that are
incongruent mod 3, such as 5 and 15.)
 if x y modm and x y modn and (m;n) = 1 then x y modmn. This was
used in the uniqueness part of the proof of the Chinese remainder theorem.
Our rst application is to counting units.
Theorem 4.1. For relatively prime positive integers m and n, '(mn) ='(m)'(n).
Page 4


THE CHINESE REMAINDER THEOREM
1. Introduction
The Chinese remainder theorem says we can uniquely solve any pair of congruences that
have relatively prime moduli.
Theorem 1.1. Let m and n be relatively prime positive integers. For any integers a and
b, the pair of congruences
xa modm; xb modn
has a solution, and this solution is uniquely determined modulo mn.
What is important here is that m and n are relatively prime. There are no constraints
at all on a and b.
Example 1.2. The congruences x 6 mod 9 and x 4 mod 11 hold when x = 15, and
more generally when x 15 mod 99, and they do not hold for any other x. The modulus
99 is 9
 11.
We will prove the Chinese remainder theorem, including a version for more than two
moduli, and see some ways it is applied to count solutions of congruences.
2. A proof of the Chinese remainder theorem
Proof. First we show there is always a solution. Then we will show it is unique modulo mn.
Existence of Solution. To show that the simultaneous congruences
xa modm; xb modn
have a common solution in Z, we give two proofs.
First proof: Write the rst congruence as an equation in Z, say x = a +my for some
y2Z. Then the second congruence is the same as
a +myb modn:
Subtracting a from both sides, we need to solve for y in
(2.1) myba modn:
Since (m;n) = 1, we know m modn is invertible. Let m
0
be an inverse for m modn,
so mm
0
 1 modn. Multiplying through (2.1) by m
0
, we have y m
0
(ba) modn, so
ym
0
(ba) +nz where z2Z. Then
x =a +my =a +m(m
0
(ba) +nz) =a +mm
0
(ba) +mnz:
1
So if x satises the original two congruences it must have this form. Let's now check this
expression, for every z2Z, really satises the original two congruences:
a +mm
0
(ba) +mnza + 0 + 0a modm
and
a +mm
0
(ba) +mnza + 1(ba) + 0b modn:
Second proof: Write both congruences as equations in Z: x = a +my and x = b +nz
for integers y and z that need to be determined. (Why would it be a bad idea to write
x = a +my and x = b +ny?) The integers of the form a +my are the numbers that
are congruent to a modm, and the integers of the form b +nz are the numbers that are
congruent to b modn. Finding a common solution to the two congruences amounts to
nding y and z in Z such that
a +my =b +nz;
which is the same as
(2.2) mynz =ba:
Can we nd such y and z for any a, b, m, and n where (m;n) = 1? Bezout's identity tells
us 1 is aZ-linear combination ofm andn, and therefore any integer isZ-linear combination
of m and n (why?). Therefore integers y and z satisfying (2.2) exist.
Uniqueness of Solution. If x =c and x =c
0
both satisfy
xa modm; xb modn;
then we have c c
0
modm and c c
0
modn. Then mj (cc
0
) and nj (cc
0
). Since
(m;n) = 1, the product mn divides cc
0
, which means c c
0
modmn. This shows any
two solutions to the initial pair of congruences are the same modulo mn. 
3. Extension to more than two congruences
The Chinese remainder theorem can be extended from two congruences to any nite
number of congruences, but we have to be careful about the way in which the moduli are
relatively prime. Consider the three congruences
x 1 mod 6; x 4 mod 10; x 7 mod 15:
While there is no common factor of 6, 10, and 15 greater than 1, these congruences do not
admit a common solution: any solution to the rst congruence is odd, while any solution
to the second congruence is even. When we have more than two moduli, we have to be
sensitive to the dierence between saying numbers are collectively relatively prime (no
common factor greater than 1 divides them all) and pairwise relatively prime (no common
factor greater than 1 divides any two of the numbers). For instance, 6, 10, and 15 are
collectively relatively prime but not pairwise relatively prime. Here is a more general form
of the Chinese remainder theorem.
Theorem 3.1. For r 2, let m
1
;m
2
;:::;m
r
be nonzero integers that are pairwise rela-
tively prime: (m
i
;m
j
) = 1 for i6= j. Then, for any integers a
1
;a
2
;:::;a
r
, the system of
congruences
xa
1
modm
1
; xa
2
modm
2
; :::; xa
r
modm
r
;
has a solution, and this solution is uniquely determined modulo m
1
m
2



m
r
.
Example3.2. The congruencesx 1 mod 3,x 2 mod 5,x 2 mod 7 are satised when
x = 37, more generally for any x 37 mod 105 and for no other x. Note 105 = 3
 5
 7.
Proof. First we show there is always a solution. Then we will show it is unique modulo
m
1
m
2



m
r
.
Existence of Solution. We argue by induction on r. The base case r = 2 is Theorem
1.1, which has been proved already.
Now we pass to the inductive step. Suppose all simultaneous congruences with r pairwise
relatively prime moduli can be solved. Consider a system of simultaneous congruences with
r + 1 pairwise relatively prime moduli:
xa
1
modm
1
; :::; xa
r
modm
r
; xa
r+1
modm
r+1
;
where (m
i
;m
j
) = 1 for all i6= j and the a
i
's are arbitrary. By the inductive hypothesis,
there is a solution b to the rst r congruences, say
ba
1
modm
1
; ba
2
modm
2
; :::; ba
r
modm
r
:
Now consider the system of two congruences
(3.1) xb modm
1
m
2



m
r
; xa
r+1
modm
r+1
:
Since (m
i
;m
r+1
) = 1 fori = 1; 2;:::;r, we have (m
1
m
2



m
r
;m
r+1
) = 1, so the two moduli
in (3.1) are relatively prime. Then by the case of two congruences, namely Theorem 1.1,
there is a solution to (3.1). Call it c. Since cb modm
1
m
2



m
r
, we have cb modm
i
for i = 1; 2;:::;r. From the choice of b we have ba
i
modm
i
for i = 1; 2;:::;r. Therefore
c a
i
modm
i
for i = 1; 2;:::;r. Also, c a
r+1
modm
r+1
from the choice of c, so we see
c satises the r + 1 given congruences.
This concludes the inductive step, so a solution exists.
Uniqueness of Solution. If x =c and x =c
0
both satisfy
xa
1
modm
1
; xa
2
modm
2
; :::; xa
r
modm
r
;
then we have c c
0
modm
i
for i = 1; 2;:::;r, so m
i
j (cc
0
) for i = 1; 2;:::;r. Since the
m
i
's are pairwise relatively prime, their product m
1
m
2



m
r
divides cc
0
, which means
cc
0
modm
1
m
2



m
r
. This shows any two solutions to the given system of congruences
are the same when viewed modulo m
1
m
2



m
r
. 
4. Applications
The signicance of the Chinese remainder theorem is that it often reduces a question
about modulusmn, where (m;n) = 1, to the same question for modulusm andn separately.
In this way, questions about modular arithmetic can often be reduced to the special case of
prime power moduli. We will see how this works for several counting problems, often using
two features of modular arithmetic with two moduli:
 if djm it makes sense to reduce integers mod m to integers mod d: if xy modm
then x y modd. For example, if x y mod 10 then x y mod 5 since if xy
is divisible by 10 then it is also divisible by 5. (In contrast, it makes no sense to
reduce x mod 10 to x mod 3, since there are congruent numbers mod 10 that are
incongruent mod 3, such as 5 and 15.)
 if x y modm and x y modn and (m;n) = 1 then x y modmn. This was
used in the uniqueness part of the proof of the Chinese remainder theorem.
Our rst application is to counting units.
Theorem 4.1. For relatively prime positive integers m and n, '(mn) ='(m)'(n).
Proof. We work with the sets
U
m
=fa modm; (a;m) = 1g; U
n
=fb modn; (b;n) = 1g;
U
mn
=fc modmn; (c;mn) = 1g:
ThenjU
m
j = '(m),jU
n
j = '(n), andjU
mn
j = '(mn). To show '(mn) = '(m)'(n), we
will write down a bijection between U
mn
and U
m
U
n
, which implies the two sets have the
same size, and that is what the theorem is saying (sincejU
m
U
n
j ='(m)'(n)).
Let f : U
mn
!U
m
U
n
by the rule
f(c modmn) = (c modm;c modn):
For c2 U
mn
, we have (c;mn) = 1, so (c;m) and (c;n) equal 1, so c modm and c modn
are units. Let's stop for a moment to take a look at an example of this function.
Take m = 3 and n = 5: U
3
=f1; 2g, U
5
=f1; 2; 3; 4g, and U
15
=f1; 2; 4; 7; 8; 11; 13; 14g.
The following table shows the values of the function f on each number in U
15
. Notice that
the values ll up all of U
3
U
5
without repetition.
c mod 15 f(c mod 15)
1 (1; 1)
2 (2; 2)
4 (4; 4) = (1; 4)
7 (7; 7) = (1; 2)
8 (8; 8) = (2; 3)
11 (11; 11) = (2; 1)
13 (13; 13) = (1; 3)
14 (14; 14) = (2; 4)
There are 2 units modulo 3 and 4 units modulo 5, leading to 8 ordered pairs of units modulo
3 and units modulo 5: (1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), and (2,4). All these pairs
show up (and just once) in the second column of the table.
We return to the general situation and show f : U
mn
!U
m
U
n
is a bijection.
To see that f is one-to-one, suppose f(k modm) = f(` modn) Then k ` modm and
k` modn, so since (m;n) = 1 (aha!), we have k` modmn. That means k =` inU
mn
,
so f is one-to-one.
Now we show f is onto. Pick any pair (a modm;b modn)2 U
m
U
n
. By the Chinese
remainder theorem we can solve ca modm and cb modn for a c2Z. Is (c;mn) = 1?
Since a modm is a unit and ca modm, c modm is a unit so (c;m) = 1. Since b modn
is a unit andcb modn,c modn is a unit so (c;n) = 1. From (c;m) = 1 and (c;n) = 1 we
get (c;mn) = 1, soc2U
mn
. From the congruence conditions onc, we havef(c) = (a;b). 
Corollary 4.2. For a positive integer m,
'(m) =m
Y
pjm

1
1
p

;
where the product runs over the primes p dividing m.
Proof. The formula is clear for m = 1 (interpreting an empty product as 1).
Now suppose m> 1, and factor m into prime powers:
m =p
e
1
1
p
e
2
2



p
er
r
:
Page 5


THE CHINESE REMAINDER THEOREM
1. Introduction
The Chinese remainder theorem says we can uniquely solve any pair of congruences that
have relatively prime moduli.
Theorem 1.1. Let m and n be relatively prime positive integers. For any integers a and
b, the pair of congruences
xa modm; xb modn
has a solution, and this solution is uniquely determined modulo mn.
What is important here is that m and n are relatively prime. There are no constraints
at all on a and b.
Example 1.2. The congruences x 6 mod 9 and x 4 mod 11 hold when x = 15, and
more generally when x 15 mod 99, and they do not hold for any other x. The modulus
99 is 9
 11.
We will prove the Chinese remainder theorem, including a version for more than two
moduli, and see some ways it is applied to count solutions of congruences.
2. A proof of the Chinese remainder theorem
Proof. First we show there is always a solution. Then we will show it is unique modulo mn.
Existence of Solution. To show that the simultaneous congruences
xa modm; xb modn
have a common solution in Z, we give two proofs.
First proof: Write the rst congruence as an equation in Z, say x = a +my for some
y2Z. Then the second congruence is the same as
a +myb modn:
Subtracting a from both sides, we need to solve for y in
(2.1) myba modn:
Since (m;n) = 1, we know m modn is invertible. Let m
0
be an inverse for m modn,
so mm
0
 1 modn. Multiplying through (2.1) by m
0
, we have y m
0
(ba) modn, so
ym
0
(ba) +nz where z2Z. Then
x =a +my =a +m(m
0
(ba) +nz) =a +mm
0
(ba) +mnz:
1
So if x satises the original two congruences it must have this form. Let's now check this
expression, for every z2Z, really satises the original two congruences:
a +mm
0
(ba) +mnza + 0 + 0a modm
and
a +mm
0
(ba) +mnza + 1(ba) + 0b modn:
Second proof: Write both congruences as equations in Z: x = a +my and x = b +nz
for integers y and z that need to be determined. (Why would it be a bad idea to write
x = a +my and x = b +ny?) The integers of the form a +my are the numbers that
are congruent to a modm, and the integers of the form b +nz are the numbers that are
congruent to b modn. Finding a common solution to the two congruences amounts to
nding y and z in Z such that
a +my =b +nz;
which is the same as
(2.2) mynz =ba:
Can we nd such y and z for any a, b, m, and n where (m;n) = 1? Bezout's identity tells
us 1 is aZ-linear combination ofm andn, and therefore any integer isZ-linear combination
of m and n (why?). Therefore integers y and z satisfying (2.2) exist.
Uniqueness of Solution. If x =c and x =c
0
both satisfy
xa modm; xb modn;
then we have c c
0
modm and c c
0
modn. Then mj (cc
0
) and nj (cc
0
). Since
(m;n) = 1, the product mn divides cc
0
, which means c c
0
modmn. This shows any
two solutions to the initial pair of congruences are the same modulo mn. 
3. Extension to more than two congruences
The Chinese remainder theorem can be extended from two congruences to any nite
number of congruences, but we have to be careful about the way in which the moduli are
relatively prime. Consider the three congruences
x 1 mod 6; x 4 mod 10; x 7 mod 15:
While there is no common factor of 6, 10, and 15 greater than 1, these congruences do not
admit a common solution: any solution to the rst congruence is odd, while any solution
to the second congruence is even. When we have more than two moduli, we have to be
sensitive to the dierence between saying numbers are collectively relatively prime (no
common factor greater than 1 divides them all) and pairwise relatively prime (no common
factor greater than 1 divides any two of the numbers). For instance, 6, 10, and 15 are
collectively relatively prime but not pairwise relatively prime. Here is a more general form
of the Chinese remainder theorem.
Theorem 3.1. For r 2, let m
1
;m
2
;:::;m
r
be nonzero integers that are pairwise rela-
tively prime: (m
i
;m
j
) = 1 for i6= j. Then, for any integers a
1
;a
2
;:::;a
r
, the system of
congruences
xa
1
modm
1
; xa
2
modm
2
; :::; xa
r
modm
r
;
has a solution, and this solution is uniquely determined modulo m
1
m
2



m
r
.
Example3.2. The congruencesx 1 mod 3,x 2 mod 5,x 2 mod 7 are satised when
x = 37, more generally for any x 37 mod 105 and for no other x. Note 105 = 3
 5
 7.
Proof. First we show there is always a solution. Then we will show it is unique modulo
m
1
m
2



m
r
.
Existence of Solution. We argue by induction on r. The base case r = 2 is Theorem
1.1, which has been proved already.
Now we pass to the inductive step. Suppose all simultaneous congruences with r pairwise
relatively prime moduli can be solved. Consider a system of simultaneous congruences with
r + 1 pairwise relatively prime moduli:
xa
1
modm
1
; :::; xa
r
modm
r
; xa
r+1
modm
r+1
;
where (m
i
;m
j
) = 1 for all i6= j and the a
i
's are arbitrary. By the inductive hypothesis,
there is a solution b to the rst r congruences, say
ba
1
modm
1
; ba
2
modm
2
; :::; ba
r
modm
r
:
Now consider the system of two congruences
(3.1) xb modm
1
m
2



m
r
; xa
r+1
modm
r+1
:
Since (m
i
;m
r+1
) = 1 fori = 1; 2;:::;r, we have (m
1
m
2



m
r
;m
r+1
) = 1, so the two moduli
in (3.1) are relatively prime. Then by the case of two congruences, namely Theorem 1.1,
there is a solution to (3.1). Call it c. Since cb modm
1
m
2



m
r
, we have cb modm
i
for i = 1; 2;:::;r. From the choice of b we have ba
i
modm
i
for i = 1; 2;:::;r. Therefore
c a
i
modm
i
for i = 1; 2;:::;r. Also, c a
r+1
modm
r+1
from the choice of c, so we see
c satises the r + 1 given congruences.
This concludes the inductive step, so a solution exists.
Uniqueness of Solution. If x =c and x =c
0
both satisfy
xa
1
modm
1
; xa
2
modm
2
; :::; xa
r
modm
r
;
then we have c c
0
modm
i
for i = 1; 2;:::;r, so m
i
j (cc
0
) for i = 1; 2;:::;r. Since the
m
i
's are pairwise relatively prime, their product m
1
m
2



m
r
divides cc
0
, which means
cc
0
modm
1
m
2



m
r
. This shows any two solutions to the given system of congruences
are the same when viewed modulo m
1
m
2



m
r
. 
4. Applications
The signicance of the Chinese remainder theorem is that it often reduces a question
about modulusmn, where (m;n) = 1, to the same question for modulusm andn separately.
In this way, questions about modular arithmetic can often be reduced to the special case of
prime power moduli. We will see how this works for several counting problems, often using
two features of modular arithmetic with two moduli:
 if djm it makes sense to reduce integers mod m to integers mod d: if xy modm
then x y modd. For example, if x y mod 10 then x y mod 5 since if xy
is divisible by 10 then it is also divisible by 5. (In contrast, it makes no sense to
reduce x mod 10 to x mod 3, since there are congruent numbers mod 10 that are
incongruent mod 3, such as 5 and 15.)
 if x y modm and x y modn and (m;n) = 1 then x y modmn. This was
used in the uniqueness part of the proof of the Chinese remainder theorem.
Our rst application is to counting units.
Theorem 4.1. For relatively prime positive integers m and n, '(mn) ='(m)'(n).
Proof. We work with the sets
U
m
=fa modm; (a;m) = 1g; U
n
=fb modn; (b;n) = 1g;
U
mn
=fc modmn; (c;mn) = 1g:
ThenjU
m
j = '(m),jU
n
j = '(n), andjU
mn
j = '(mn). To show '(mn) = '(m)'(n), we
will write down a bijection between U
mn
and U
m
U
n
, which implies the two sets have the
same size, and that is what the theorem is saying (sincejU
m
U
n
j ='(m)'(n)).
Let f : U
mn
!U
m
U
n
by the rule
f(c modmn) = (c modm;c modn):
For c2 U
mn
, we have (c;mn) = 1, so (c;m) and (c;n) equal 1, so c modm and c modn
are units. Let's stop for a moment to take a look at an example of this function.
Take m = 3 and n = 5: U
3
=f1; 2g, U
5
=f1; 2; 3; 4g, and U
15
=f1; 2; 4; 7; 8; 11; 13; 14g.
The following table shows the values of the function f on each number in U
15
. Notice that
the values ll up all of U
3
U
5
without repetition.
c mod 15 f(c mod 15)
1 (1; 1)
2 (2; 2)
4 (4; 4) = (1; 4)
7 (7; 7) = (1; 2)
8 (8; 8) = (2; 3)
11 (11; 11) = (2; 1)
13 (13; 13) = (1; 3)
14 (14; 14) = (2; 4)
There are 2 units modulo 3 and 4 units modulo 5, leading to 8 ordered pairs of units modulo
3 and units modulo 5: (1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), and (2,4). All these pairs
show up (and just once) in the second column of the table.
We return to the general situation and show f : U
mn
!U
m
U
n
is a bijection.
To see that f is one-to-one, suppose f(k modm) = f(` modn) Then k ` modm and
k` modn, so since (m;n) = 1 (aha!), we have k` modmn. That means k =` inU
mn
,
so f is one-to-one.
Now we show f is onto. Pick any pair (a modm;b modn)2 U
m
U
n
. By the Chinese
remainder theorem we can solve ca modm and cb modn for a c2Z. Is (c;mn) = 1?
Since a modm is a unit and ca modm, c modm is a unit so (c;m) = 1. Since b modn
is a unit andcb modn,c modn is a unit so (c;n) = 1. From (c;m) = 1 and (c;n) = 1 we
get (c;mn) = 1, soc2U
mn
. From the congruence conditions onc, we havef(c) = (a;b). 
Corollary 4.2. For a positive integer m,
'(m) =m
Y
pjm

1
1
p

;
where the product runs over the primes p dividing m.
Proof. The formula is clear for m = 1 (interpreting an empty product as 1).
Now suppose m> 1, and factor m into prime powers:
m =p
e
1
1
p
e
2
2



p
er
r
:
The p
e
i
i
's are pairwise relatively prime. By an extension of Theorem 4.1 from two relatively
prime terms to any number of pairwise relatively prime terms (just induct on the number
of terms), we have
'(m) ='(p
e
1
1
)'(p
e
2
2
)


'(p
er
r
):
Now using the formula for ' on prime powers,
'(m) = p
e
1
1
1
(p
1
 1)p
e
2
1
2
(p
2
 1)


p
er1
r
(p
r
 1)
= p
e
1
1

1
1
p
1

p
e
2
2

1
1
p
2




p
er
r

1
1
p
r

= m
Y
pjm

1
1
p

:

Example 4.3. To compute '(540) ='(2
2

 3
3

 5), we have
'(540) = 540

1
1
2

1
1
3

1
1
5

= 540

1
2


2
3


4
5
= 18
 8
= 144:
An alternate calculation is
'(540) = '(4)'(27)'(5)
= (4 2)(27 9)(5 1)
= 2
 18
 4
= 144:
We now leave units mod m and look at squares mod m.
Theorem4.4. For m2Z
+
with m 2, let S
m
=fx
2
modmg be the set of squares modulo
m. When (m;n) = 1,jS
mn
j =jS
m
j
jS
n
j.
Note S
m
is all squares modulo m, including 0. So S
5
=f0; 1; 4g, for example.
Proof. We will use the Chinese remainder theorem twice.
If a x
2
modmn then a x
2
modm and a x
2
modn. Thus any square modulo mn
reduces to a square modulo m and a square modulo n. So we have a function f : S
mn
!
S
m
S
n
by f(a modmn) = (a modm;a modn). Let's take a look at an example.
Setm = 3 andn = 5, soS
3
=f0; 1g, S
5
=f0; 1; 4g andS
15
=f0; 1; 4; 6; 9; 10g. The table
below gives the values of f on S
15
. The values ll up S
3
S
5
without repetition.
c mod 15 f(c mod 15)
0 (0; 0)
1 (1; 1)
4 (4; 4) = (1; 4)
6 (6; 6) = (0; 1)
9 (9; 9) = (0; 4)
10 (10; 10) = (1; 0)