68 CHAPTER 2 Discrete Mathematics
covers 74 kilometers after biking for 2 hours, jogging for 3 hours,
and swimming for 4 hours, while Sue covers 91 kilometers after
jogging for 2 hours, swimming for 3 hours, and biking for 4 hours.
Their biking, jogging, and swimming rates are all whole numbers
in kilometers per hour. Find these rates.2.1.3 The Chinese remainder theorem
Congruence and The Integers Modulo n. If n is a positive
integer, and ifa andb are integers, we say that a is congruent to
b modulo n and write a ≡ b(modn) if n|(a−b). Next, we write
Zn ={ (^0) n, (^1) n, (^2) n,...,(n−1)n}with the understanding that ifbis any
integer, and ifb=qn+r, where 0≤r < n, thenbn=rn. Sometimes
we get lazy and just writeZn={ 0 , 1 , 2 ,...,n− 1 }without writing the
subscripts if there is no possibility of confusion. As an example, we see
thatZ 6 ={ 0 , 1 , 2 , 3 , 4 , 5 }with such further stipulations as 8 = 2, 22 =
4 , −5 = 1. The integers modulo n can be added (and multiplied)
pretty much as ordinary integers, we just need to remember to reduce
the answer modulon.
Example. We can write out the sums and products of integers modulo
6 conveniently in tables:
- 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 0
2 2 3 4 5 0 1
3 3 4 5 0 1 2
4 4 5 0 2 3 4
5 5 0 1 2 3 4
· 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1
The following story^7 conveys the spirit of the Chinese Remainder
Theorem:
(^7) Apparantly due to the Indian mathematician Brahmagupta (598–670).