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.

Proof

• 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$.

Let us define the set $S$ as:

$S = \left\{{x \in \Z: x = a - z b, z \in \Z, x \ge 0}\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 \implies \exists q \in \Z: 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$.

• 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 a\)	\(=\)	\(\displaystyle q_1 b + r_1, 0 \le r_1 < b\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle q_2 b + r_2, 0 \le r_2 < b\)	\(\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$.

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

Now, 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 a\)	\(=\)	\(\displaystyle -\left \vert {a} \right \vert\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle -\left({\tilde q b - \tilde r}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle b \left({-\tilde q}\right) + \left({- \tilde r}\right)\)	\(\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 a\)	\(=\)	\(\displaystyle b \left({-\tilde q}\right) + \left({- \tilde r}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle b \left({-\tilde q}\right) - b + b - \tilde r\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle b \left({-1 - \tilde q}\right) + \left({b - \tilde r}\right)\)	\(\displaystyle \)

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

• 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$.

That finishes the proof.

$\blacksquare$

Alternative (Informal and Handwavey) 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 \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$

Comment

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.

Sources

• Seth Warner: Modern Algebra (1965): $\S 24$: Theorem $24.1$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\S 0.1$: Theorem $2$
• C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 3.10$: Theorem $18$
• B. Hartley and T.O. Hawkes: Rings, Modules and Linear Algebra (1970): $\S 2.3$
• George E. Andrews: Number Theory (1971): $\S 2.1$: Theorem $2.1$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 21$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 11.1$
• John F. Humphreys: A Course in Group Theory (1996): $\text{A}.1$: Theorem $\text{A}.1$