1.7 The division algorithm with remainder
Let \(n\in \mathbb {Z}\) and let \(d\in \mathbb {P}\). Then there there exists integers \(q\) and \(r\) such that
\(n = qd + r\).
\(0 \leq r {\lt} d\).
Moreover, the integers \(q\) and \(r\) are unique. The integer \(q\) is called the quotient and the integer \(r\) is called the remainder. We write \(\operatorname{\mathrm{Mod}}(n,d) := r\).
Let \(S\) denote the set of all nonnegative integers, which can be written in the form \(n -qd\) with \(q\in \mathbb {Z}\).
If \(n{\gt}0\), then the set \(S\) is obviously nonempty as \(n\in S\). If \(n = 0\), then, taking \(q = -1\), we see that \(d\in S\). And, if \(n {\lt} 0\), then, taking \(q = -n\), we see that \(-n(1+d) \in S\).
So we can find a smallest element \(r\in S\) and write it in the form \(r = n - qd\). By definition, \(r\) satisfies 1. On the other hand, if \(r \geq d\), then \(0 \leq n - qd - d = n - (q+1)d = r - d {\lt} r\), which is a contradiction. So \(r\) satisfies 2 as well.
To see uniqueness, suppose \(n = q_1d+r_1 = q_2d+r_2\) with both \((q_1,d_1)\) and \((q_2,r_2)\) satisfying the properties satisfied by \((q,d)\) in 1 and 2. Without loss of generality, we can assume that \(r_1 \leq r_2\). And then we have \(0\leq r_2 - r_1 {\lt} d\). Then, since \(q1 d + r_1 = q_2d + r_2\), we have that \((q_1 - q_2)d = (r_2 -r_1)\). And since \(0\leq r_2 -r_1 {\lt} d\), this implies that \(r_2 - r_1 = q_1 - q_2 = 0\) proving the uniqueness of the pair \((q,r)\) in the theorem.
One of the nice things about the proof of Theorem 1.11 is that it gives an algorithm to compute \(q\) and \(r\). It’s not a very effective one. But here’s what it says in the case that \(n {\gt} 0\):
Set \(r = n\) and \(q = 0\).
If \(r {\lt} d\), stop. Otherwise, replace \(r\) by \(r - d\) and \(q\) by \(q+1\).
Repeat step 2 until you stop.
Another nice thing about the proof is that it stays within integers.
But there’s another way to think about the division algorithm if we’re willing to use the rational (or even real) numbers.
Suppose \(x\in \mathbb {R}\). The floor \(\lfloor x\rfloor \) of \(x\) is the largest integer \(n\) such that \(n\leq x\).
The existence of the floor \(\lfloor x \rfloor \) follows from a variant of the well-ordered property of \(\mathbb {N}\). (It is also basically obvious.) Moreover, we have
If \(x\in \mathbb {R}\), then \(x-1 {\lt} \lfloor x\rfloor \leq x\).
Exercise.
Suppose \(n\in \mathbb {Z}\) and \(d\in \mathbb {P}\). Write \(n = qd + r\) as in Theorem 1.11. Then \(q = \lfloor n/d\rfloor \) and \(r = n - qd = n - d\lfloor n/d\rfloor \).
From Lemma 1.13, we get that
Multiplying through in the above equation by \(d\) and then subtracting the answers from \(n\), we get that
So we’re done by the uniqueness of \(q\) and \(r\) in Theorem 1.11.