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

CHAP. 11] PROPERTIES OF THE INTEGERS 289

11.23. Leta= 23 · 35 · 54 · 116 · 173 andb= 25 · 53 · 72 · 114 · 132. Find gcd(a, b)and lcm(a, b).

Those primespiwhich appear in bothaandbwill also appear in gcd(a, b). Furthermore, the exponent ofpi

in gcd(a, b) will be the smaller of its exponents inaandb. Hence

gcd(a, b)= 23 · 53 · 114

Those primespiwhich appear in eitheraorbwill also appear in lcm(a, b). Also, the exponent ofpiin lcm(a, b)

will be the larger of its exponent in a andb. Hence

lcm(a, b)= 25 · 35 · 54 · 72 · 116 · 132 · 173

11.24. Prove Theorem 11.9: Supposea, b, care integers.

(i) Ifa|bandb|c, thena|c. (iv) Ifa|bandb=0, thena=±bor|a|<|b|.

(ii) Ifa|bthen, for any integerx,a|bx. (v) Ifa|bandb|a, then|a|=|b|, that is,a=±b.

(iii) Ifa|banda|c, thena|(b+c)anda|(b−c). (vi) Ifa|1, thena=±1.

(i) Ifa|bandb|c, then there exist integersxandysuch thatax=bandby=c. Replacingbbyax, we obtain

axy=c. Hencea|c.

(ii) Ifa|b, then there exists an integercsuch thatac=b. Multiplying the equation byx, we obtainacx=bx.

Hencea|bx.

(iii) Ifa|banda|c, then there exist integersxandysuch thatax=banday=c. Adding the equalities, we obtain

ax+ay=b+c and so a(x+y)=b+c

Hencea|(b+c). Subtracting the equalitiesay=bandby=c,we obtain

ax−ay=b−c andso a(x−y)=b−c.

Thusa|(b−c).

(iv) Ifa|b, then there existscsuch thatac=b. Then

|b|=|ac|=|a||c|

Hence either|c|=1or|a|<|a||c|=|b|.If|c|=1, thenc=±1; wherea=±b, as required.

(v) Ifa|b, thena=±bor|a|<|b|.If|a|<|b|thenb|a.Hencea=±b.

(vi) Ifa|1, thena=±1or|a|<| 1 |=1. By Problem 11.11,|a|≥1. Therefore,a=±1.

11.25. A nonempty subsetJofZis called anidealifJhas the following two properties:

(1) Ifa, b∈J, thena+b∈J. (2) Ifa∈Jandn∈Z, thenna∈J.

Letdbe the least positive integer in an idealJ={ 0 }. Prove thatddivides every element ofJ.

SinceJ={ 0 }, there existsa∈Jwitha=0. Then−a=(− 1 )a∈J. ThusJcontains positive elements. By

the Well-Ordering Principle,Jcontains a least positive integer, sodexists. Now letb∈J. Dividingbbyd, the

division algorithm tells us there existqandrsuch that

b=qd+r and 0≤r<d

Nowb, d∈JandJis an ideal; henceb+(−q)d=ralso belongs toJ. By the minimal property ofd, we must

haver=0. Henced|b, as required.

11.26. Prove Theorem 11.13: Letdbe the smallest positive integer of the formax+by.Thend=gcd(a, b).

Consider the setJ={ax+yb|x, y∈Z}. Then

a= 1 (a)+ 0 (b)∈J and b= 0 (a)+ 1 (b)∈J