# The Division Algorithm

## Statement of the Algorithm

The division algorithm is one of the basic structural facts about the integers. It says that any integer can be divided by a positive integer with a unique quotient and remainder.

Let $a\in\mathbb{Z}$ and let $b\in\mathbb{N}$. Then there exist unique integers $q$ and $r$ such that

$$
a=bq+r,
$$

where

$$
0\le r<b.
$$

The integer $q$ is called the quotient, and $r$ is called the remainder.

For example, if

$$
a=29,
\qquad
b=5,
$$

then

$$
29=5\cdot5+4.
$$

Thus the quotient is $5$, and the remainder is $4$.

## Meaning of the Remainder

The remainder measures the part of $a$ left after subtracting the largest suitable multiple of $b$.

For instance,

$$
29=5\cdot5+4
$$

means that $5\cdot5=25$ is the largest multiple of $5$ not exceeding $29$, and the remaining part is $4$.

The condition

$$
0\le r<b
$$

is essential. It ensures that the remainder is chosen from exactly one of the possibilities

$$
0,1,2,\ldots,b-1.
$$

Without this condition, many decompositions would be possible. For example,

$$
29=5\cdot5+4
$$

but also

$$
29=5\cdot4+9.
$$

Only the first has a remainder between $0$ and $4$.

## Divisibility as Zero Remainder

The division algorithm connects division with divisibility.

For integers $a$ and positive $b$,

$$
b\mid a
$$

if and only if the remainder on division of $a$ by $b$ is $0$.

Indeed, if $b\mid a$, then

$$
a=bq
$$

for some integer $q$, so

$$
a=bq+0.
$$

Conversely, if

$$
a=bq+0,
$$

then

$$
a=bq,
$$

and therefore

$$
b\mid a.
$$

Thus divisibility is exact division, while the division algorithm describes the general case.

## Examples

Dividing $43$ by $7$, we obtain

$$
43=7\cdot6+1.
$$

Thus

$$
q=6,
\qquad
r=1.
$$

Dividing $100$ by $9$, we get

$$
100=9\cdot11+1.
$$

Dividing $84$ by $12$, we get

$$
84=12\cdot7+0.
$$

The zero remainder shows that

$$
12\mid84.
$$

Negative dividends are also allowed. For example, dividing $-17$ by $5$, we require

$$
0\le r<5.
$$

The correct expression is

$$
-17=5(-4)+3.
$$

Thus

$$
q=-4,
\qquad
r=3.
$$

Although

$$
-17=5(-3)-2,
$$

this expression does not satisfy the required condition because the remainder is negative.

## Existence

We sketch why the quotient and remainder must exist.

Let $a\in\mathbb{Z}$ and $b\in\mathbb{N}$. Consider the set

$$
S=\{a-bq:q\in\mathbb{Z},\ a-bq\ge0\}.
$$

This set contains all nonnegative integers obtained by subtracting multiples of $b$ from $a$.

The set $S$ is nonempty. By taking $q$ sufficiently negative, the number $a-bq$ becomes positive.

By the well-ordering principle, $S$ has a least element. Call it $r$. Then

$$
r=a-bq
$$

for some integer $q$, so

$$
a=bq+r.
$$

It remains to show that

$$
r<b.
$$

If $r\ge b$, then

$$
r-b\ge0.
$$

But

$$
r-b=a-bq-b=a-b(q+1),
$$

so $r-b$ also belongs to $S$. This contradicts the minimality of $r$. Therefore

$$
0\le r<b.
$$

## Uniqueness

Suppose there are two decompositions:

$$
a=bq+r
$$

and

$$
a=bq'+r',
$$

where

$$
0\le r<b,
\qquad
0\le r'<b.
$$

Subtracting the two equations gives

$$
b(q-q')=r'-r.
$$

Thus

$$
b\mid(r'-r).
$$

But since $r$ and $r'$ both lie between $0$ and $b-1$, we have

$$
-(b-1)\le r'-r\le b-1.
$$

The only multiple of $b$ in this range is $0$. Hence

$$
r'-r=0.
$$

So

$$
r=r'.
$$

Then

$$
b(q-q')=0,
$$

which gives

$$
q=q'.
$$

Therefore the quotient and remainder are unique.

## Division into Residue Classes

The possible remainders modulo $b$ are

$$
0,1,2,\ldots,b-1.
$$

Every integer belongs to exactly one of these remainder classes.

For example, modulo $5$, every integer has one of the remainders

$$
0,1,2,3,4.
$$

Thus the division algorithm partitions the integers into five classes:

$$
5q,\quad 5q+1,\quad 5q+2,\quad 5q+3,\quad 5q+4.
$$

This idea is the foundation of congruence arithmetic.

## Role in Number Theory

The division algorithm is the basis of many central tools in number theory.

It underlies the Euclidean algorithm, which computes greatest common divisors. It defines remainders, which lead to congruences and modular arithmetic. It also provides the structure needed for proofs involving minimal counterexamples and descent.

Although the statement is elementary, its consequences are extensive. Much of elementary number theory begins with the simple fact that every integer can be written uniquely as

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