Home » Division Algorithm

Tag: Division Algorithm

Prove the division algorithm by induction

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