Division algorithm

The next result basically says that, for $b>0$ every integer $a$ occurs in one of the columns in the array (1.1) above. It also goes by the name ``long division''.

Theorem 1.2.7 (Division algorithm)   Let $a$ and $b>0$ be integers. There are integers $q$ (the quotient) and $r$ (the remainder) such that

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

Furthermore, $q$ and $r$ are unique.

Our proof of the division algorithm depends on the following axiom.

Axiom 1.2.8 (Well-ordering principle)   Each non-empty set of natural numbers contains a least element.

In particular, each set $S$ of integers which contains at least one non-negative element must contain a smallest non-negative element. Furthermore, this smallest element is unique.

We begin the proof of the division algorithm by showing that $q$ and $r$ are unique. Suppose $a=bq+r=bq_1+r_1$ , where $0 \leq r <b$ , $0 \leq r_1 < b$ . Then $0=b(q-q_1)+(r-r_1)$ . Since $b$ divides the right side and the first term of the left side of the above equation, $b$ must divide $r-r_1$ . But $-b < r-r_1 < b$ , so $r-r_1=0$ . Therefore $r$ is unique. Since $bq+r=bq_1+r_1$ , this in turn implies $q$ is also unique.

We present two proofs of the existence of $q$ and $r$ in the division algorithm.

First proof of Division algorithm: First, we claim that $a$ must lie in between some two consecutive elements of

$$b\mathbb{Z}=\{...,-2b,-b,0,b,2b,...\},$$

say $qb\leq a < (q+1)b$ (see (1.1) for a visual representation of this idea). Then $0\leq a-qb<b$ . Therefore, $a=qb+r$ , where $r=a-qb$ . This proves the division algorithm, assuming the truth of the claim (which is left as an exercise).

Second proof of Division algorithm: Consider the set

$$S=a+b\mathbb{Z}=\{a+nb \vert n\in \mathbb{Z}\} =\{...,a-2b,a-b,a,a+b,a+2b,...\}.$$

This contains at least one non-negative element, for example, $a+\vert a\vert b\geq a+\vert a\vert\geq 0$ . By the well-ordering principle, $S$ contains a least non-negative element, say $r$ . By definition of $S$ , there is an integer $q$ such that $r=a-qb$ . It remains to show $r<b$ . Suppose not (to get a contradiction), i.e., suppose $r\geq b$ . Then $0\leq r-b=a+(-q-1)b\in S$ , and $r-b<r$ , so $r$ was not the smallest non-negative element of $S$ . This contradiction shows that the hypothesis $r\geq b$ is false. Therefore $r<b$ and the proof is complete. $\Box$

About 200 years ago in Germany, at the age of 23 C. F. Gauss ^1.1published Disquisitiones Arithmeticae, essentially an expanded version of his PhD thesis, that revolutionized the study of number theory. One piece of new notation which Gauss introduced is the congruence or modulus notation. Let $a,b,m$ be integers. We say that $a$ is congruent to $b$ modulo $m$ , written

$$a\equiv b ({\rm mod} m),$$

if $m\vert(a-b)$ . In this case, $m$ is called the modulus and $b$ is a residue of $a$ modulo $m$ .

The division algorithm may be restated in this new notation as follows.

Theorem 1.2.9   If $a$ and $m>0$ are integers then there is an integer $r\in \{0,1,...,m-1\}$ satisfying

$$a\equiv r ({\rm mod} m) .$$

In other words, each integer has a residue mod $m$ (called the least residue) ) which is in the range $0,1,...,m-1$ . Furthermore, this residue can be computed using the division algorithm.

Example 1.2.10   We have

• $71\equiv 1 ({\rm mod} 7)$ ,
• $147\equiv 3 ({\rm mod} 12)$ ,
• $km\equiv 0 ({\rm mod} m)$ for any integers $k$ and $m>0$ , and
• $-1\equiv 10 ({\rm mod} 11)$ .