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

CHAP. 11] PROPERTIES OF THE INTEGERS 297

CRT tells us there is a unique solution moduloM= 21 ·10 = 210. Adding multiples of the modulusm=21 to the

given solutionx=11 of the equation(d), we obtain the following 10 solutions of (d) which are less than 210:

11 , 32 , 53 , 74 , 95 , 116 , 137 , 158 , 179 , 210

Testing each of these solutions of(d)in the equation(c), we find thatx=116 is the only solution of equation(c).

Accordingly,x=116 is the smallest positive integer satisfying all of the three given equations(a),(b), and(c).

Method 2:Using the notation of Proposition 11.30, we obtain

M= 3 · 7 · 10 = 210 ,M 1 = 210 / 3 = 70 ,M 2 = 210 / 7 = 30 ,M 3 = 210 / 10 = 21

We now seek solutions to the equations

70 x≡ 1 (mod 3), 30 x≡ 1 (mod 7), 21 x≡ 1 (mod 10)

Reducing 70 modulo 3, reducing 30 modulo 7, and reducing 21 modulo 10, we obtain the equivalent system

x≡ 1 (mod 3), 2 x≡ 1 (mod 7), x≡ 1 (mod 10)

The solutions of these three equations are, respectively,

s 1 = 1 ,s 2 = 4 ,s 3 = 1

Substituting into the formula

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

we obtain the following solution of our original system:

x 0 = 70 · 1 · 2 + 30 · 4 · 4 + 21 · 1 · 6 = 746

Dividing this solution by the modulusM=210, we obtain the remainderx=116 which is the unique solution of

the original system between 0 and 210.

11.57. Prove Theorem 11.26: Ifaandmare relatively prime, thenax≡1 (modm) has a unique solution;

otherwise it has no solution.

Supposex 0 is a solution. Thenmdividesax 0 −1, and hence there existsy 0 such thatmy 0 =ax 0 −1.

Therefore

ax 0 +my 0 = 1 (11.14)

andaandmare coprime (relatively prime). Conversely, ifaandmare coprime, then there existx 0 andy 0 satisfying

(11.14), in which casex 0 is a solution ofax≡1 (modm).

It remains to prove thatx 0 is a unique solution modulom. Supposex 1 is another solution. Then

ax 0 ≡ 1 ≡ax 1 (modm)

Sinceaandmare coprime, the Modified Cancellation Law holds here, so

x 0 ≡x 1 (modm)

Thus the theorem is proved.

11.58. Prove Theorem 11.27: Supposeaandmare relatively prime. Thenax≡b(modm) has a unique

solution. Moreover, ifsis the unique solution ofax≡1 (modm), thenx=bsis the unique solution to

ax≡b(modm).

By Theorem 11.26 (proved in Problem 11.57), a unique solutionsofax≡1 (modm) exists. Henceas≡ 1

(modm) and so

a(bs)=(as)b≡ 1 ·b=b(modm)

That is,x=bsis a solution ofax≡b(modm). Supposex 0 andx 1 are two such solutions. Then

ax 0 ≡b≡ax 1 (modm)

Sinceaandmare coprime, the Modified Cancellation Law tells us thatx 0 ≡x 1 (modm). That is,ax≡b(modm)

has a unique solution modulom.