The Division Algorithm

One rather important aspect of the divisibility of integers is that if $a, b \in \mathbb{Z}$ then $a$ can be written as the product of some quotient $q$ with $b$ plus a remainder $r$. For example, if $a = 11$ and $b = 3$, then $a = 3(b) + 2$ where $q = 3$ and $r = 2$.

The following theorem known as the Division Algorithm shows us that for any pair of integers $a, b \in \mathbb{Z}$ where $b > 0$ that the form $a = bq + r$ exists and is unique.

Theorem 1 (The Division Algorithm): Let $a, b \in \mathbb{Z}$ with $b > 0$. Then there exists unique $q, r \in \mathbb{Z}$ where $0 \leq r < b$ and such that $a = bq + r$.

The value of $r$ is often called the Remainder when $a$ is divided by $b$. That is, $a$ is equal to some multiple $q$, known as the Quotient of $b$, plus a remainder $r$ for which $0 \leq r < b$.

• Proof: Let $a, b \in \mathbb{Z}$ with $b > 0$ and consider the following set $A$:

(1)

\begin{align} \quad A = \{ a - bq : q \in \mathbb{N} \} = \{ a, a - b, a - 2b, ... \}. \end{align}

• Consider $B \subset A$ of nonnegative elements in $A$. If $a > 0$ then $a \in B$ and if $a < 0$ then $a - ba = a(1 - b) \in B$, so $B$ is a nonempty set. Moreover, $B$ is a nonempty subset of integers and so by the Well-Ordering principle there exists a least element of $B$, say $r \in B$ is this least element. Since $r \in B$ we have that $r = a - bn$ for some $n \in \mathbb{N}$ and so:

(2)

\begin{align} \quad a = bq + r \end{align}

• So $a$ if of the form we desire. Now since $r \in B$ and every element in $B$ is nonnegative then we have that $0 \leq r$. Suppose that $r \geq b$. Then $r = b + p$ where $p \geq 0$ and so:

(3)

\begin{align} \quad a = bq + r = bq + (b + p) = b(q + 1) + p \end{align}

• Therefore $p = a - b(q + 1) \geq 0$ and so $p \in B$. Since $b > 0$ and $q+1 > q$ we have that $0 \leq p < r$. But this implies that $r$ is not the least element of $B$ which is a contradiction, so our assumption that $r \geq b$ is false, and so $0 \leq r < b$.

• We lastly show that $q$ and $r$ are unique for $a = bq + r$ and $0 \leq r < b$. Suppose that $a = bq_1 + r_1$ and $a = bq_2 + r_2$ where $0 \leq r_1, r_2 < b$. Then by subtracting these two equations we get:

(4)

\begin{align} \quad 0 = bq_1 - bq_2 + r_1 - r_2 \\ \quad 0 =b(q_1 - q_2) + r_1 - r_2 \\ \quad r_2 - r_1 = b(q_1 - q_2) \end{align}

• Therefore $r_2 - r_1$ is a multiple of $b$. Since $0 \leq r_1 < b$ and $0 \leq r_2 < b$ we must have that $-b < r_2 - r_1 < b$. The only multiple of $b$ such that $-b < r_2 - r_1 < b$ is $0$, so:

(5)

\begin{align} \quad r_2 - r_1 = 0 \\ \quad r_1 = r_2 \end{align}

• Since $r_1 = r_2 = r$, we have that $0 = b(q_1 - q_2)$. Since $b > 0$ this implies that $q_1 - q_2 = 0$ and so $q_1 = q_2$. Therefore $a$ can be uniquely expressed in the form $a = bq + r$ where $0 \leq r < b$. $\blacksquare$