Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

298 PROPERTIES OF THE INTEGERS [CHAP. 11

11.59. Prove Theorem 11.28: Consider the following equation whered=gcd(a, m):

ax≡b(mod m) (11.15)

(i) Supposeddoes not divideb. Then (11.15) has no solution.

(ii) Supposeddoes divideb. Then (11.15) hasdsolutions which are all congruent moduloMto the unique solution

of the following equation whereA=a/d, B=b/d, M=m/d:

Ax≡B(mod M) (11.16)

(i) Supposex 0 is a solution of (11.15). Thenax 0 ≡b(modm), and somdividesax 0 −b. Thus there exists an

integery 0 such thatmy 0 =ax 0 −bormy 0 +ax 0 =b. Butd=gcd(a, m), and soddividesmy 0 +ax 0. That

is,ddividesb. Accordingly, ifddoes not divideb, then no solution exists.

(ii) Supposex 0 is a solution of (11.15). Then, as above,

my 0 +ax 0 =b

Dividing through bydwe get (11.16). HenceMdividesAx 0 −Band sox 0 is a solution of (11.16). Conversely,

supposex 1 is a solution of (11.16). Then, as above, there exists an integery 1 such that

My 1 +Ax 1 =B

Multiplying through bydyields

dMy 1 +dAx 1 =dB or my 1 +ax 1 =b

Thereforemdividesax 1 −bwhencex 1 is a solution of (11.15). Thus (11.16) has the same integer solution.

Letx 0 be the unique smallest positive solutions of (11.16). Sincem=dM,

x 0 ,x 0 +M, x 0 + 2 M, x 0 + 3 M, ..., x 0 +(d− 1 )M

are precisely the solution of (11.16) and (11.15) between 0 andm. Thus (11.15) hasdsolutions modulom, and

all are congruent tox 0 moduloM.

11.60. Prove the Chinese Remainder Theorem (Theorem 11.29:) Given the system:

x≡r 1 (mod m 1 ), x≡r 2 (mod m 2 ), ..., x≡rk(mod mk) (11.17)

where the mi are pairwise relatively prime. Then the system has a unique solution modulo

M=m 1 m 2 ···mk.

Consider the integer

x 0 =M 1 s 1 r 1 +M 2 s 2 r 2 +···+Mkskrk

whereMi=M/miandsiis the unique solution ofMix≡1 (modmi). Letjbe given.

Fori=j, we havemj|Miand hence

Misiri≡ 0 (modmj)

On the other hand,MjSj≡1 (modmj); and hence

Mjsjrj≡rj(modmj)

Accordingly,

x 0 ≡ 0 +···+ 0 +rj+ 0 +···+ 0 ≡rj(modmj)

In other words,x 0 is a solution of each of the equations in (11.17).

It remains to show thatx 0 is the unique solution of the system (11.17) moduloM.

Supposex 1 is another solution of all the equations in (11.17). Then:

x 0 ≡x 1 (modm 1 ), x 0 ≡x 1 (modm 2 ), ···,x 0 ≡x 1 (modmk)

Hencemi|(x 0 −x 1 ), for eachi. Since themiare relatively prime,M=lcm(m 1 ,m 2 ,...,mk)and soM|(x 0 −x 1 ).

That is,x 0 =x 1 (modM). Thus the theorem is proved.