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

290 PROPERTIES OF THE INTEGERS [CHAP. 11

Also, supposes,t∈J, say,s=x 1 a+y 1 bandt=x 2 a+y 2 b. Then, for anyn∈Z, the following belong toJ:

s+t=(x 1 +x 2 )a+(y 1 +y 2 )b and ns=(nx 1 )a+(ny 1 )b

ThusJis an ideal. Letdbe the least positive element inJ. We claimd=gcd(a, b).

By the preceding Problem 11.25,ddivides every element ofJ. Thus, in particular,ddividesaandb. Now

supposehdivides bothaandb. Thenhdividesxa+ybfor anyxandy; that is,hdivides every element ofJ. Thus

hdividesd, and soh≤d. Accordingly,d=gcd(a, b).

11.27. Prove Theorem 11.17: Suppose gcd(a, b)=1, andaandbdividec. Thenabdividesc.

Since gcd(a, b)=1, there existxandysuch thatax+by=1. Sincea|candb|c, there existmandnsuch

thatc=maandc=nb. Multiplyingax+by=1bycyields

acx+bcy=c or a(nb)x+b(ma)y=c or ab(nx+my )=c

Thusabdividesc.

11.28. Prove Corollary 11.19: Suppose a primepdivides a productab. Thenp|aorp|b.

Supposepdoes not dividea. Then gcd(p, a)=1 since the only divisors ofpare±1 and±p. Thus there

exist integersmandnsuch that 1=mp+nq. Multiplying bybyieldsb=mp b+nab. By hypothesis,p|ab, say,

ab=cp. Then:

b=mp b+nab=mp b+ncp=p(mb+nc).

Hencep|b, as required.

11.29. Prove: (a) Supposep|qwherepandqare primes. Thenp=q.
(b) Supposep|q 1 q 2 ···qrwherepand theq’s are primes. Thenpis equal to one of theq’s.

(a) The only divisors ofqare±1 and±q. Sincep> 1 ,p=q.

(b)Ifr=1, thenp=q 1 by (a). Supposer>1. By Problem 11.28 (Corollary 11.19)p|q 1 orp|(q 2 ···qr).

If p|q 1 ,

thenp=q 1 by (a). If not, thenp|(q 2 ···qr). We repeat the argument. That is, we getp=p 2 orp|(q 3 ···qr).

Finally (or by induction)pmust equal one of theq’s.

11.30. Prove the Fundamental Theorem of Arithmetic (Theorem 11.20): Every integern>1 can be expressed
uniquely (except for order) as a product of primes.
We already proved Theorem 11.11 that such a product of primes exists. Hence we need only show that such a
product is unique (except for order). Suppose

n=p 1 p 2 ···pk=q 1 q 2 ···qr

where thep’s andq’s are primes. Note thatp 1 |(q 1 q 2 ···qr). By the preceding Problem 11.29,p 1 equals one of the

q’s. We rearrange theq’s so thatp 1 =q 1. Then

p 1 p 2 ···pk=p 1 q 2 ···qr and so p 2 ···pk=q 2 ···qr

By the same argument, we can rearrange the remainingq’s so thatp 2 =q 2. And so on. Thusncan be expressed

uniquely as a product of primes (except for order).

CONGRUENCES

11.31. Which of the following are true?

(a) 446≡278 (mod 7), (c) 269≡413 (mod 12), (e) 445≡536 (mod 18)

(b) 793≡682 (mod 9), (d) 473≡369 (mod 26), (f) 383≡126 (mod 15)

Recalla≡b(modm) if and only ifmdividesa−b.