Division Theorem

Theorem

For every pair of integers $a, b$ where $b \ne 0$, there exist unique integers $q, r$ such that $a = q b + r$ and $0 \le r < \left|{b}\right|$:

$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \left|{b}\right|$

In the above equation:

• $q$ is called the quotient
• $r$ is called the principal remainder, or, more usually, just the remainder.

Formal Proof

Non-Negative Integers

First we need to prove $\forall a, b \in \Z, a \ge 0, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$.

That is, we prove the theorem for non-negative $a$ and positive $b$.

Proof of Existence

Let us define $S$ as the set of all positive integers of the form $a - z b$ where $z$ is an integer:

$S = \left\{{x \in \Z_{\ge 0}: x = a - z b \text{for some } z \in \Z}\right\}$

$S \ne \varnothing$ because, by putting $z = 0$, we find that $a \in S$.

Now $S$ is bounded below by $0$ and therefore has a least element, which we will call $r$.

Thus:

$\exists q \in \Z: a - q b = r$

and so:

$a = q b + r$

So we have proved the existence of $q$ and $r$ such that $a = q b + r$.

Now we need to show that $0 \le r < b$.

We already know that $0 \le r$ as $r \in S$ and is therefore bounded below by $0$.

Suppose $b \le r$. As $b > 0$, we see that $r < r + b$.

Thus $b \le r < r + b \implies 0 \le r - b < r$.

So $r - b = \left({a - q b}\right) - b = a - b \left({q + 1}\right)$.

So $r - b \in S$ as it is of the correct form.

But $r - b < r$ contradicts the choice of $r$ as the least element of $S$.

Hence $r < b$ as required.

So we have now established the existence of $q$ and $r$ satisfying $a = q b + r, 0 \le r < b$.

Proof of Uniqueness

Now we need to prove that $q$ and $r$ are unique.

Suppose $q_1, r_1$ and $q_2, r_2$ are two pairs of $q, r$ that satisfy $a = q b + r, 0 \le r < b$.

That is:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle \)	\(\displaystyle q_1 b + r_1, 0 \le r_1 < b\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle \)	\(\displaystyle q_2 b + r_2, 0 \le r_2 < b\)	\(\displaystyle \)	\(\displaystyle \)

This gives $0 = b \left({q_1 - q_2}\right) + \left({r_1 - r_2}\right)$.

If $q_1 \ne q_2$, let $q_1 > q_2 \implies q_1 - q_2 \ge 1$.

Since $b > 0$, we get $r_2 - r_1 = b \left({q_1 - q_2}\right) \ge b \times 1 = b$.

So $r_2 \ge r_1 + b \ge b$ which contradicts the assumption that $r_2 < b$.

Similarly for if $q_1 < q_2$.

Therefore $q_1 = q_2$ and so $r_1 = r_2$, and so $q$ and $r$ are unique after all.

Thus we have proved the Division Theorem for $a \ge 0, b > 0$.

Negative $a$

Now we need to prove the Theorem for $a < 0$.

We know that:

$\exists \tilde q, \tilde r \in \Z: \left|{a}\right| = \tilde q b + \tilde r, 0 \le \tilde r < b$

Since $\left \vert {a} \right \vert = -a$, this gives:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle \)	\(\displaystyle -\left \vert {a} \right \vert\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle -\left({\tilde q b + \tilde r}\right)\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle b \left({-\tilde q}\right) + \left({- \tilde r}\right)\)	\(\displaystyle \)	\(\displaystyle \)

If $\tilde r = 0$, then $q = -\tilde q, r = \tilde r = 0$, which gives $a = q b + r, 0 \le r < b$ as required.

Otherwise we have $0 < \tilde r < b \implies 0 < b - \tilde r < b$, which suggests we rearrange the expression for $a$ above:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle \)	\(\displaystyle b \left({-\tilde q}\right) + \left({- \tilde r}\right)\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle b \left({-\tilde q}\right) - b + b - \tilde r\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle b \left({-1 - \tilde q}\right) + \left({b - \tilde r}\right)\)	\(\displaystyle \)	\(\displaystyle \)

Now if we take $q = \left({-1 - \tilde q}\right)$ and $r = \left({b - \tilde r}\right)$, we have the required result.

Negative $b$

Now the proof is extended to take on negative values of $b$.

Let $b < 0$.

Consider $\left|{b}\right| = -b > 0$.

By the above, we have the existence of $\tilde q, \tilde r \in \Z$ such that $a = \tilde q \left|{b}\right| + \tilde r, 0 \le \tilde r < \left|{b}\right|$.

Since $\left|{b}\right| = -b$, we have:

$a = \tilde q \left({-b}\right) + \left({\tilde r}\right) = \left({-\tilde q}\right) b + \tilde r$

We define $q = -\tilde q, r = \tilde r$ and we have proved the existence of integers that satisfy the requirements.

The proof that they are unique is the same as that for the proof for positive $b$, but with $\left|{b}\right|$ replacing $b$.

$\blacksquare$

Informal Proof

Show Existence

Consider the progression:

$\ldots,a-3b,a-2b,a-b,a,a+b,a+2b,a+3b,\ldots$

which extends in both directions.

Then by the Well-Ordering Principle, there must exist a smallest non-negative element, denoted by $r$.

So $r = a - q b$ for some $q \in \Z$.

$r$ must be in the interval $\left[{0, b}\right)$ because otherwise $r-b$ would be smaller than $r$ and a non-negative element in progression.

Show Uniqueness

Assume we have another pair $q_0$ and $r_0$ such that $a = b q_0 + r_0$, with $0 \le r_0 < b$.

Then $b q + r = b q_0 + r_0$.

Factoring we see that $r - r_0 = b \left({q_0 - q}\right)$, and so $b \mathop \backslash \left({r - r_0}\right)$.

Since $0 \le r < b$ and $0 \le r_0 < b$, we have that $-b < r - r_0 < b$.

Hence, $r - r_0 = 0 \implies r = r_0$.

So now $r - r_0 = 0 = b \left({q_0 - q}\right)$ which implies that $q = q_0$.

Therefore solution is unique.

$\blacksquare$

Proof from Basis Representation Theorem

If $b = 1$ it follows that $r = 0$ and $q = a$.

Let $b > 1$.

Suppose that $a > 0$.

By the Basis Representation Theorem, $a$ has a unique representation to the base $b$:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle \)	\(\displaystyle \sum_{k \mathop = 0}^s r_k b^k\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle b \sum_{k \mathop = 0}^{s-1} r_k b^{k-1} + r_0\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle b q + r\)	\(\displaystyle \)	\(\displaystyle \)	where $0 \le r = r_0 < b$

If a second pair $q', r'$ existed, there would be a representation for $q'$ to the base $b$:

$\displaystyle q' = \sum_{k \mathop = 0}^t u_k b^k$

so that:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle \)	\(\displaystyle b q' + r'\)	\(\displaystyle \)	\(\displaystyle \)	$0 \le r < b$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle \sum_{k \mathop = 0}^t u_k b^{k+1} + r'\)	\(\displaystyle \)	\(\displaystyle \)

But there already exists a representation of $a$ to the base $b$:

$\displaystyle a = \sum_{k \mathop = 0}^s r_k b^k$

By the Basis Representation Theorem, such a representation is unique.

So:

$t = s - 1$

$u_k = r_{k+1}$

$r' = a_0 = r$

and hence $q = q$.

So the proposition holds for $a > 0$.

$\Box$

If $a = 0$ it follows that $q = r = 0$ is the only possible solution with $0 \le r < b$.

$\Box$

Let $a < 0$.

Then $-a > 0$ and it follows from the above that there exist unique $q'', r''$ such that:

$-a = k q'' + r''$

If $r'' = 0$ then:

$a = b \left({-q''}\right)$

and we take $q = -q''$ and $r = 0$.

If $r'' \ne 0$ then:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle \)	\(\displaystyle - b q'' = r''\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \)	\(\displaystyle a \left({-q'' - 1}\right) + \left({b - r''}\right)\)	\(\displaystyle \)	\(\displaystyle \)

and we may take $q = -q'' - 1$ and $r = b - r''$.

In either case $q$ and $r$ satisfy the conditions.

Uniqueness for $a < 0$ follow from uniqueness for $-a > 0$ which is positive.

$\blacksquare$

Also known as

Otherwise known as the Quotient Theorem, or (more specifically) the Quotient-Remainder Theorem (as there are several other "quotient theorems" around).

Some sources call this the division algorithm but it is preferable not to offer up a possible source of confusion between this and the Euclidean Algorithm to which it is closely related.

It is also known by some as Euclid's Division Lemma, and by others as the Euclidean Division Property.

Sources

• Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts (1951)... (previous)... (next): Introduction $\S 6$: The division process in $I$
• Richard A. Dean: Elements of Abstract Algebra (1966)... (previous)... (next): $\S 0.1$: Theorem $2$
• B. Hartley and T.O. Hawkes: Rings, Modules and Linear Algebra (1970)... (previous)... (next): $\S 2.3$: Some properties of subrings and ideals
• Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory (1971): $\S 8.28$