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

CHAP. 11] PROPERTIES OF THE INTEGERS 285

11.10. Supposenis a positive integer. Proven≥1. (This is not true for the rational numbersQ.) In other words,
ifP (n)is the statement thatn≥1, thenP (n)is true for everyn∈N.
P (n)holds forn=1 since 1≥1. AssumingP(k)is true, that is,k≥1, add 1 to both sides to obtain

k+ 1 ≥ 1 + 1 = 2 > 1

This isP(k+ 1 ). ThusP(k+ 1 )is true wheneverP(k)is true. By the principle of mathematical induction,Pis true

for everyn∈N.

11.11. Supposeaandbare positive integers. Prove:

(a)Ifb=1, thena<ab.

(b)Ifab=1, thena=1 andb=1.

(c)Ifnis composite, thenn=abwhere 1<a,b<n.

(a) By Problem 11.10,b>1. Henceb− 1 >0, that is,b−1 is positive. By the property [P 1 ] of the positive

integersN, the following product is also positive:

a(b− 1 )=ab−a

Thusa<ab, as required.

(b) Supposeb=1. By (a),a<ab=1. This contradicts Problem 11.10; henceb=1. It then follows thata=1.

(c)Ifnis not prime, thennhas a positive divisorasuch thata=1 anda=n. Thenn=abwhereb=1 and

b=n. Thus, by Problem 11.10 and by part (a), 1<a,b<ab=n.

11.12. Prove Theorem 11.6 (Well-Ordering Principle): LetSbe a nonempty set of positive integers. ThenS
contains a least element.
SupposeShas no least element. LetMconsist of those positive integers which are less than every element ofS.
Then 1∈M; otherwise, 1∈Sand 1 would be a least element ofS. Supposek∈M. Thenkis less than every
element ofS. Thereforek+ 1 ∈M; otherwisek+1 would be a least element ofS.
By the Principle of Mathematical Induction,Mcontains every positive integer. ThusSis empty which contradicts
the hypothesis thatSis nonempty. Accordingly, the original assumption thatShas no least element cannot be true.
Thus the theorem is true.

11.13. Prove Theorem 11.5 (Induction: Second Form): LetPbe a proposition defined on the integersn≥ 1
such that: (i)P( 1 )is true. (ii)P(k)is true wheneverP(j)is true for all 1≤j<k.
ThenPis true for alln≥1.
LetAbe the set of integersn≥1 for whichPis not true. SupposeAis not empty. By the Well-Ordering
Principle, A contains at least elementa 0 By (i),a 0 =1.
Sincea 0 is the least element ofA,Pis true for every integerjwhere 1≤j<a 0. By (ii),Pis true fora 0. This
contradicts the fact thata 0 ∈A. HenceAis empty, and soPis true for every integern>1.

DIVISION ALGORITHM

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

(a) a=258 andb=12; (b)a=573 andb=−16.

(a) Hereaandbare positive. Simply divideabyb, that is, 258 by 12, say by long division, to obtain the quotient

q=21 and remainderr=6. Alternately, using a calculator, we get

258 / 12 = 21. 5 ,q=INT(a/b)= 21 ,r=a−bq= 258 − 12 ( 21 )= 6