Proofs utilizing the Well-Ordering Property This question comes directly from as an example in Chapter 5.2 of Rosen's Discrete Mathematics and It's Applications textbook on page 341.
Use the well-ordering property to prove the division algorithm. Recall that the division algorithm states that if a is an integer and d is a positive integer, then there are unique integers q and r with 0 ≤ r < d and a = dq + r.
Solution: Let S be the set of nonnegative integers of the form a − dq, where q is an integer. This set is nonempty because −dq can be made as large as desired (taking q to be a negative integer with large absolute value). By the well-ordering property, S has a least element r = a − dq0.
The integer r is nonnegative. It is also the case that r < d. If it were not, then there would be a smaller nonnegative element in S, namely, a − d(q0 + 1). To see this, suppose that r ≥ d. Because a=dq0+r, it follows that a−d(q0+1)=(a−dq0)−d=r−d≥0. Consequently, there are integers q and r with 0 ≤ r < d. 
Here are my questions: 


*

*Why we are considering a set S of remainders r? How does that relate to proving the correctness of the division algorithm?

*What is a better explanation of why r < d?

*What is a set of actual numbers that I can use to test this proof on?
My apologies if this question is not clear. This is my first post on StackExchange. Please let me know if I can clarify anything. 
Thanks!
 A: $1:$ We consider the set of remainders because the goal of the proof is to show that there is a unique smallest remainder. If we weren't considering a set of remainders, then we would not be able to use the well-ordering principle to state that there is a smallest remainder.
$2:$ Suppose $r \geq d$. Then subtract $d$ from $r$ and increment $q$ to obtain a smaller value of $r$, while preserving equality. Repeating this process guarantees that $r < d$.
$$a = dq + r = dq + r -d + d$$
$$dq + r -d + d = dq + d + (r-d) = d(q+1) + (r-d)$$
As you can see, the final equality is in the appropriate form for the division algorithm, but with the smaller remainder $(r-d)$. If $r \geq d$, then clearly $r-d \geq 0$ (subtract $d$ from both sides).
$3:$ Any pair of integers. Repeatedly subtract the divisor from $a$ to get different remainders (most larger than $d$). These remainders form $S$, and you just proved that $S$ has a minimum value, which gives your solution. The number of subtractions performed is $q$.
A: *

*He's using the set of remainders to prove it in full generality. Try to verifiy the proof locally, take some integers and divide them by any other number, see what happens if $d=r$ and $d<r$, just as I wrote below. This will give you a local intuition about the proof. Now there is one question (a very important one): How does one generalize this result? How do you know that for any natural number $x$ divided by any other natural number gives you a unique remainder? For this, the author is using some important properties of the set of natural numbers.

*Suppose the remainder could be equal to $d$, then you could do the following: $dq+r=d(q+1)+0$. For example: $6=2\cdot 2+2=6=2\cdot 3+0$ . (That is, if $r=d$, you could take this $r$ and then put it into the product $dq$ and then the reminder would equal $0$). Now try to do the same thing for a remainder bigger than $d$ and see what happens. (Remember: Try some examples first, and then try to prove it).

*Well, you can test on pretty much any number. Take $7$, divide by $3$, it'll give you $7=2\cdot 3+1$, now try divide it by $4$. Notices that divide means that you need to do integer division: A division that yields exactly $dq+r$. On the case above, $7=\stackrel{d}{3} \cdot \stackrel{q}{2}+\stackrel{r}{1}$.
