Question

In this exercise we outline a proof of the following statement, which we will be taking for granted in our proof of the division theorem: If a, b ∈ Z with b > 0, the set

S = {a − bq : q ∈ Z and a − bq ≥ 0}

has a least element.

(a) Prove the claim in the case 0 ∈ S.

(b) Prove the claim in the case 0 ∈/ S and a > 0. (0 is not a member of S)

(c) Prove the claim in the case 0 ∈/ S and a ≤ 0. (0 is not a member of S)

Answer 1

Solution:

Given that,

Division Theorem:

If a,bz with b>0,

S={a-bq:qz and a-bq0}

Well-ordering principle:

Every non-empty set of non-negative integers contains a least element.

a) we assume 0s

So,s and S is a set of non negative integers so by well ordering principle , S has a least element.

b) 0S and a>0

Then,take, q=0z,

we have,

a-bq=a>0

Thus,as

so ,by same logic,s has a least element.

c) 0s and a0

Take,q=az

Then,a-bq=a-ab=a(1_b)0

[since, b>0b1(1_b)0 and a0]

Thus,a_abs

so,by same logic,s has a least element.

Note that the cases(a),(b),(c) exhant all possible cases.

Thus,

s has a least elements.

Then. the lemma is proved.