70 CHAPTER 2 Discrete Mathematics
m 3 = 1 3. Therefore, we are really faced with the task of finding the
smallest integermsatisfying
m 4 = 1 4 , m 5 = 1 5 , m 6 = 1 6 , m 7 = 0 7.The first question that should occur to the reader is “why is there
any solution m to the above?” As we’ll see, this will be the point of
emphasis in the Chinese Remainder Theorem.
Theorem. (Chinese Remainder Theorem) Let a and b be positive
integers, and setd= gcd(a,b). Letxandybe any two integers satifying
xd=yd. Then there is always an integermsuch that
ma=xa, mb=yb.Furthermore, if l = lcm(a,b) then any other solutionm′is congruent
tommodulol.
Proof. First of all sincexd=ydwe know thatd|(x−y); assume that
x−y=zd, for some integerz. Next, letsandtbe integers satisfying
sa+tb=d, from this we obtain
sza+tzb=zd=x−y.From this we see thatx−sza = y+tzb; we now take m to be this
common value: m=x−sza =y+tzb from which it is obvious that
ma=xaandmb=yb.
Finally, ifm′is another solution, then we havem′≡m(moda) and
m′≡m(modb) and som′−mis a multiple of bothaandb. Therefore
l|(m′−m) and som′≡m(modl) proving the theorem.
We’ll consider a couple of examples.Example 1. Solve the simultaneous congruences
m ≡ 14(mod 138)
m ≡ 23(mod 855).