For all \(a,b \in \mathbb{Z}\) with \(b > 0\), there exists unique \(q,r \in \mathbb{Z}\) such that $$ \begin{aligned} a = bq + r \end{aligned} $$ with \(0 \leq r < b\).

Proof

Consider the following set

$$ \begin{align*} S = \{a - bx \mid x \in \mathbb{Z}, a - bx \geq 0\} \end{align*} $$
Side note: for example, if \(a = 12\) and \(b = 5\), then \(S = \{2,7,12,17,22,\cdots\}\).
\(x\)\(-1\)\(0\)\(1\)\(2\)\(3\)
\(a-bx\)\(17\)\(12\)\(7\)\(2\)\(-3\)
Note here that when \(x = 3\), then \(12 - 5(3) = -3 \not\in S\). So only when \(a - bx \geq 0\), then the element is in \(S\). Also note that if \(x = 1\) for example, then \(q = 1\) and \(r = 7\). This means that \(a = qb + r = 1(5) + 7 = 12\). But, observe that \(r \not< b\). So this doesn't satisfy the division algorithm's requirement. The only value that will satisfy this is the minimum element in \(S\). That is when \(x = 2\), then here \(r = 2 < b\).

Observe now that \(S\) is set of non-negative integers. Therefore, by the well ordering principle, if \(S\) is not empty, then \(S\) has a minimum element. Then, we claim that \(S\) is non-empty. So we have two cases

case \(a \geq 0\): Then if we take \(x = 0\), then \(a - b(0) = a \in S\). So \(S\) is non-empty and therefore has a minimum element by the well ordering principle.

case \(a < 0\): Then, take \(x = a\). Observe now that \(a - ba = a(1- b)\). Since \(b > 0\), then \(1 - b \leq 0\). Furthermore, since \(a < 0\), then \(a - ba \geq 0\). So \(a - ba \in S\). Therefore, \(S\) is non-empty and has a minimum element by the well ordering principle.

Now, let \(r\) be the minimum element of \(S\) and \(q\) be the corresponding \(x\) value. We want to show that \(0 \leq r < b\). Suppose for the sake of contradiction that \(r \geq b\). Then

$$ \begin{align*} r = a - qb \geq b \end{align*} $$

Now subtract \(b\) from both sides to see that

$$ \begin{align*} r - b &= a - qb - b \geq b - b \\ r - b &= a - b(q+1) \geq 0 \end{align*} $$

But this shows that \(r - b\) can be written in terms of \(a\) and \(b\) and is also greater or equal to zero. So \(r - b\) is an element in \(S\). This is contradiction since \(r\) is the minimum element in \(S\) and \(r - b < r\). Therefore, \(r < b\) as required.

Next, we want to show that \(q\) and \(r\) are unique. So suppose for the sake of contradiction that they were not. Then, suppose

$$ \begin{align*} a = qb + r = q'b + r' \quad \text{where } 0 \leq r,r' < b \end{align*} $$

Re-arrange the terms to see that

$$ \begin{align*} bq + r &= bq' + r' \\ bq' - bq &= r' - r \\ b(q' - q) &= r' - r \end{align*} $$

Assume without the loss of generality that \(q' > q\). Then this implies that \(b(q'-q) \geq b\). Then

$$ \begin{align*} r' - r = b(q' - q) \geq b \end{align*} $$

This is a contradiction since we know that \(0 \leq r, r' < b\). This means that \(r' - r < b\). Therefore, \(q = q'\) and \(r = r'\). \(\blacksquare\)

References