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

where

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

For example, if

then

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,

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

The condition

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

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

but also

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$,

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

Indeed, if $b\mid a$, then

for some integer $q$, so

Conversely, if

then

and therefore

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

Examples

Dividing $43$ by $7$, we obtain

Thus

Dividing $100$ by $9$, we get

Dividing $84$ by $12$, we get

The zero remainder shows that

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

The correct expression is

Thus

Although

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

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

for some integer $q$, so

It remains to show that

If $r\ge b$, then

But

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

Uniqueness

Suppose there are two decompositions:

and

where

Subtracting the two equations gives

Thus

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

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

So

Then

which gives

Therefore the quotient and remainder are unique.

Division into Residue Classes

The possible remainders modulo $b$ are

Every integer belongs to exactly one of these remainder classes.

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

Thus the division algorithm partitions the integers into five classes:

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