Problem 7. (40 points) In this problem, you will prove that division with remainder is welldefined. 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 < a, and there exists an integer q for which b = aq + r.

(a) (20 points) Prove that if r1 and r2 are both remainders after the division of b by a, then r1 = r2 (that is, there is at most one remainder). You can use without proof reasonable facts about integer multiplication, addition, subtraction, and >, but dont 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 0 : 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).