In this problem, you will prove that division with remainder is well- defined. That is, you...

Transcribed Image Text:

In this problem, you will prove that division with remainder is well- defined. That is, you will prove that for any two integers a > 0 and b, there exists a unique remainder after the division of b and a. We will do the proof in two parts: first by proving that there is at most one remainder, and then by proving that there exists at least one remainder. The conclusion will be that there exists a unique remainder. Assume a and b are both integers and a > 0. Define a remainder after the division of b by a to be a value r such that r 0, r , but don't assume anything about integer division. In particular, you can use the fact that there are no integer multiplies of a that are greater than 0 and less than a. (b) (20 points) Let S = { integer s 20: integer q such that b = aq+s}. You can use without proof the following fact: every nonempty subset of nonnegative integers contains an element that is smaller than all other values in the subset. Prove that S contains a remainder after the division of b by a (that is, there is at least one remainder). In this problem, you will prove that division with remainder is well- defined. That is, you will prove that for any two integers a > 0 and b, there exists a unique remainder after the division of b and a. We will do the proof in two parts: first by proving that there is at most one remainder, and then by proving that there exists at least one remainder. The conclusion will be that there exists a unique remainder. Assume a and b are both integers and a > 0. Define a remainder after the division of b by a to be a value r such that r 0, r , but don't assume anything about integer division. In particular, you can use the fact that there are no integer multiplies of a that are greater than 0 and less than a. (b) (20 points) Let S = { integer s 20: integer q such that b = aq+s}. You can use without proof the following fact: every nonempty subset of nonnegative integers contains an element that is smaller than all other values in the subset. Prove that S contains a remainder after the division of b by a (that is, there is at least one remainder).

Answer rating: 100% (QA)

remainders after a Le... View the full answer