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

CHAP. 11] PROPERTIES OF THE INTEGERS 287

11.18. Prove Theorem 11.8 (Division Algorithm): Letaandbbe integers withb=0. Then there exists integers
qandrsuch thata=bq+rand 0≤r′<|b|. Also, the integersqandrare unique.
LetMbe the set of nonnegative integers of the form a−xbfor some integerx.Ifx=−|a|bthena−xbis
nonnegative; henceMis nonempty. By the Well-Ordering Principle,Mhas a least element, sayr. Sincer∈M,
we have
r≥0 and r=a−qb
for some integerq. We need only show thatr<|b|. Supposer≥|b|. Letr′=r−|b|.
Thenr′≥0 and alsor′<rbecauseb=0. Furthermore,

r′=r−|b|=a−qb−|b|=

{

a−(q+ 1 )b, ifb< 0

a−(q− 1 )b, ifb> 0

In either case,r′belongs toM. This contradicts the fact thatris the least element ofMAccordingly,r<|b|. Thus the

existence ofqandris proved.

We now show thatqandrare unique. Suppose there exist integersqandrandq′andr′such that

a=bq+r and a=bq′+r′ where 0<r,r′<|b|

Thenbq+r=bq′+r′; hence

b(q−q′)=r′−r

Thusbdividesr′−r. But|r′−r|<|b|since 0<r,r′<|b|. Accordingly,r′−r=0. Sinceb=0 this

impliesq−q′=0. Consequently,r′=randq′=q; that is,qandrare uniquely determined byaandb.

DIVISIBILITY, PRIMES, GREATEST COMMON DIVISOR

11.19. Find all positive divisors of: (a) 18; (b) 256= 28 ;(c) 392= 23 · 72.

(a) Since 18 is relatively small, we simply write down all positive integers (≤18) which divide 18. These are:

1 , 2 , 3 , 6 , 9 , 18

(b) Since 2 is a prime, the positive divisors of 256= 28 are simply the lower powers of 2, i.e.,

20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28

In other words, the positive divisors of 256 are:

1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256

(c) Since 2 and 7 are prime, the positive divisors of 392= 23 · 72 are products of lower powers of 2 times lower

powers of 7, i.e.,

20 · 70 , 21 · 70 , 22 · 70 , 23 · 70 , 20 · 71 , 21 · 71 , 22 · 71 , 23 · 71 ,

20 · 72 , 21 · 72 , 22 · 72 , 23 · 72

In other words, the positive powers of 392 are:

1 , 2 , 4 , 8 , 7 , 14 , 28 , 56 , 49 , 98 , 196 , 392.

(We have used the usual convention thatn^0 =1 for any nonzero numbern.)

11.20. List all primes between 50 and 100.

Simply list all numberspbetween 50 and 100 which cannot be written as a product of two positive integers,

excluding 1 andp. This yields:

51 , 53 , 57 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 87 , 89 , 91 , 93 , 97