The Division Algorithm

The division algorithm is the conceptual underpinning of many concepts in number theory (congruence arithmetic is one example). In this post, we present a proof of the division algorithm and connect it to one important property of congruence.

This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

___________________________________________________________________________________________________________________

The Division Algorithm

The following is the statement of the division algorithm.

Let $a$ and $b$ be positive integers. Then there exist unique integers $q$ and $r$ such that

$a = q \cdot b + r$

where $0 \le r .

Let $A$ be the set $A=\left\{a-jb: j=0,1,2,3,\cdots \right\}$. Let $A_+$ be the following subset of $A$.

$A_+=\left\{x \in A: x \ge 0 \right\}$

The set $A_+$ is a set of non-negative integers. Hence it must have a least element, say $r$. Then we have $r=a-qb$ for some positive integer $q$. Furthermore, we have $0 \le r. If $r>b$, $r$ would not be the least element of $A_+$ since we can subtract $b$ into $r$ to obtain $a-(q+1)b$, which is less than $r$ and is an element of $A_+$.

We now have found integers $q$ and $r$ such that $a = q \cdot b + r$. It remains to show that the integers $q$ and $r$ are unique. Suppose there are also integers $q_0$ and $r_0$ such that

$a=q \cdot b + r=q_0 \cdot b + r_0$

After subtracting, $(q-q_0) \cdot b + (r-r_0)=0$. Since $b$ divides both $0$ and $(q-q_0) \cdot b$, $b$ must divides $r-r_0$. This means that $r-r_0=0$, since both $r$ and $r_0$ are non-negative integers that are less than $b$. Thus $r=r_0$ and in turns $q-q_0$. $\blacksquare$

Conceptually the division algorithm tells us that there is a unique remainder $r$ upon division of $a$ by $b$. In terms of actual computation, it does not tell us how to find the remainder or the quotient. However it is the conceptual underpinning of many concepts and ideas in number theory.

___________________________________________________________________________________________________________________

Congruence

We now use the division algorithm to prove one important property of congruence. The symbol $a \equiv b \ (\text{mod} \ m)$ means that $m$ divides $a-b$ (in words, we say $a$ is congruent to $b$ modulo $m$). For a basic discussion of congruence arithmetic, see “A basic discussion of congruences”. We prove the following property of congruence.

For every integer $a$, $a \equiv r \ (\text{mod} \ m)$ for a unique integer $r$ with $0 \le r.

In other words, any integer is congruence modulo $m$ to one and only one element $r$ in the set $\left\{0,1,2,\cdots,m-1 \right\}$. The integer $r$ is called the least residue of $a$ modulo $m$.

The above property about least residue follows from the division algorithm. Let $a$ be any integer. If $a=0$, clearly $a \equiv 0 \ (\text{mod} \ m)$. We can assume that $a \ne 0$.

Now consider the case that $a>0$. By the division algorithm, there are integers $q$ and $r$ such that $a=q \cdot m+r$ where $0 \le r . Thus $a \equiv r \ (\text{mod} \ m)$.

Consider the case that $a<0$. By the division algorithm, there are integers $q$ and $r$ such that $-a=q \cdot m+r$ where $0 \le r . Immediately we have $a=(-q) \cdot m+(-r)$. Thus $a \equiv -r \ (\text{mod} \ m)$. Note that $-r \equiv m-r \ (\text{mod} \ m)$. Thus $a \equiv m-r \ (\text{mod} \ m)$/

One concluding remark is that any least residue that is found in the above argument is unique. This is because no two distinct elements of the set $\left\{0,1,2,\cdots,m-1 \right\}$ can be congruent to each other. $\blacksquare$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$