Proof of the Division Algorithm

Proof of the Division Algorithm

Let $a$ and $b$ be integers with $b>0$. We want to show that there exist unique integers $q$ and $r$ such that:

$$a=bq+r,0\le r<b.$$

Consider the following set:

$$S=\{a-bx\mid a-bx\ge 0\text{ and }x\in \mathbb{Z}\}.$$

Clearly $S$ is a subset of ${\mathbb{Z}}_{\ge 0}$, to use the Well-Ordering Axiom, we need to show $S$ is nonempty. The idea is clear, since $b>0$, we can always find a $x$ which is negative enough to make $a-bx\ge 0$. More rigorously, we can choose $x=-|a|$, then we have:

$$a-b(-|a|)=a+b|a|=|a|(\pm 1+|b|)\ge 0.$$

Now apply the Well-Ordering Axiom, we know $S$ has a smallest element, denote it as $r=a-bq$. We will show that $r$ satisfy the Remainder Condition. We proceed by contradiction, suppose $r\ge b$, then we will have:

$$r-b=a-bq-b=a-b(q+1)\ge 0.$$

This implies $r-b\in S$, which contradicts the minimality of $r$. Therefore, we must have $r<b$, also $r\ge 0$ based on its construction. This completes the existence part of the Division Algorithm Theorem.

Now we will show the uniqueness part. Suppose we have two pairs of integers $(q_1,r_1)$ and $(q_2,r_2)$ that satisfy the equation:

$$a=b{q}_1+r_1=b{q}_2+r_2.$$

Subtracting the two equations, we have:

$$b(q_1-q_2)=r_2-r_1.$$

WLOG, we may assume $r_2>r_1$, then we have $0<r_2-r_1\le r_2<b$. This implies:

$$0\le b(q_1-q_2)<b.$$

Since $b>0$, we must have $q_1-q_2=0$, which implies $q_1=q_2$ and $r_1=r_2$. This completes the proof of the uniqueness part. $■$

Generalization

The Division Algorithm Theorem can be generalized to the following form:

Theorem

Let $a,b$ be integers with $b\ne 0$. Then there exist unique integers $q$ and $r$ such that:

$$a=bq+r\text{ and }0\le r<|b|.$$