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

286 PROPERTIES OF THE INTEGERS [CHAP. 11

(b) Hereais positive, butbis negative. Divideaby|b|, that is, 573 by 16, say with a calculator to obtain:

a/|b|= 573 / 16 = 35. 8125 ,q′=INT(a/|b|)= 35 ,r′= 573 − 16 ( 35 )= 13

Then

573 =( 16 )( 35 )+13 and 573=(− 16 )(− 35 )+ 13

Thusq=−35 andr=13.

11.15. For each pair of integersaandb, find integersqandrsuch thata=bq+rand 0<r<|b|:

(a) a=−381 andb=14; (b)a=−433 andb=−17.

Hereais negative in each case, hence we have to make some adjustments to be sure that 0<r<|b|.

(a) Divide|a|=381 byb=14, say with a calculator, to obtain the quotientq′=27 and remainderr′=3. Then

381 =( 14 )( 27 )+3 and so − 381 =( 14 )(− 27 )− 3

But−3 is negative and cannot be the remainderr; hence we add and subtractb=14 as follows:

− 381 =( 14 )(− 27 )− 14 + 14 − 3 =( 14 )(− 28 )+ 11

Thusq=−28 andr=11.

(b) Divide|a|=433 by|b|=17, say by a calculator, to obtain the quotientq′=25 and remainderr′=8. Then:

433 =( 17 )( 25 )+8 and so − 433 =(− 17 )( 25 )− 8

But –8 is negative and cannot be the remainderr; we correct this by adding and subtracting|b|=17 as follows:

− 433 =(− 17 )( 25 )− 17 + 17 − 8 =(− 17 )( 26 )+ 9

Thusq=26 andr=9.

11.16. Prove

√

2 is not rational, that is,

√

2 =a/bwhereaandbare integers.

Suppose

√

2 is rational and

√

2 =a/bwhereaandbare integers reduced to lowest terms, i.e., gcd(a, b)=1.

Squaring both sides yields

2 =

a^2

b^2

or a^2 = 2 b^2

Then 2 dividesa^2. Since 2 is a prime, 2 also dividesa. Saya= 2 c. Then

2 b^2 =a^2 = 4 c^2 or b^2 = 2 c^2

Then 2 dividesb^2. Since 2 is a prime 2 also dividesb. Thus 2 divides both a andb. This contradicts the assumption

that gcd(a, b)=1. Therefore,

√

2 is not rational.

11.17. Prove Theorem 11.8 (Division Algorithm) for the case of positive integers. That is, assumingaandbare
positive integers, prove there exist nonnegative integersqandrsuch that

a=bq+r and 0 ≤r<b (11.10)

Ifa<b, chooseq=0 andr=a.Ifa=b, chooseq=1 andr=0. In either case,qandrsatisfy (11.10).

The proof is now by induction ona.Ifa=1 thena<bora=b; hence the theorem holds whena=1.

Supposea>b. Thena−bis positive anda−b<a. By induction, the theorem holds fora−b. Thus there exists

q′andr′such that

a−b=bq′+r′ and 0 ≤r′<b

Then

a=bq′+b+r′=b(q′+ 1 )+r′

Chooseq=q′+1 andr=r′. Thenqandrare nonnegative integers and satisfy (11.10). Thus the theorem is

proved.