Question

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.

Answer 1

Answer:-----------

The Division Algorithm:- If a is an integer and d is a positive integer with n > 0, then there are unique integers q and r, with 0 <= r < d, and a = dq + r .

Again, this is so basic that one may doubt whether it should even be proved. But the well-ordering principle allows us, in fact, to prove the division algorithm in a rigorous manner:

Let W = { a - td | t∈ Z }
It is obvious that W contains nonnegative integers.
Let V = { v∈ Z | v >= 0}.
By the well-ordering principle, v has a smallest element, which we'll call r. r ∈ V , so r = a - qd for some q and r >= 0 (by the definition of sets W and V, correspondingly).

Now, what's left to prove is that r < n. Let's assume the opposite, namely that r = a - qd >= n .
Rearranging: r - d = a - (q + 1)d >= 0 .
By the definition of V, a - (q + 1)d ∈ V (since it has the form a - td  for some integer t and is nonnegative). But recall that we called r the smallest element of V, and a - (q + 1)d < = r , so we have a contradiction.

Therefore, we see that r < n. This completes the proof..