Division Algorithm Archives

The division algorithm states that for a fixed positive integer $b$ and for every integer $n \geq 0$ , there exist nonnegative integers $q$ and $r$ such that

$n = qb + r, \qquad 0 \leq r < b.$

Prove this by induction.

Proof. Let $b$ be a fixed positive integer. If $n=0$ then letting $q = r = 0$ , the statement is true (since $0 = 0b + 0$ ).
Now assume the statement is true for some $k \in \mathbb{Z}_{\geq 0}$ . By the induction hypothesis we know there exist nonnegative integers $q$ and $r$ such that

$k = qb + r, \qquad 0 \leq r < b.$

Thus, adding 1 to both sides we have,

$k+1 = qb + (r+1).$

Since $0 \leq r < b$ we know $0 \leq r \leq (b-1)$ . If $0 \leq r < b-1$ , then $0 \leq (r+1) < b$ , and the statement still holds with the same choice of $q$ and $r+1$ in place of $r$ .
On the other hand, if $r = b-1$ , then $r+1 = b$ and we have,

$k+1 = qb + b = (q+1)b + 0.$

Hence, the statement holds again, but with $q+1$ in place of $q$ and with $r = 0$ (which is valid since if $r = 0$ then we have $0 \leq r < b$ ). Therefore, if the division algorithm holds for $k$ , then it also holds for $k+1$ . Hence, it holds for all $n \in \mathbb{Z}_{\geq 0}. \qquad \blacksquare$

Stumbling Robot

Tag: Division Algorithm

Prove the division algorithm by induction