# Division Theorem

## Contents

## 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\lvert{b}\right\rvert$

In the above equation:

## Proof 1

From Division Theorem: Positive Divisor:

- $\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$

That is, the result holds for positive $b$.

$\Box$

It remains to show that the result also holds for negative values of $b$.

Let $b < 0$.

Consider:

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

where $\left|{b}\right|$ denotes the absolute value of $b$: by definition $\left|{b}\right| > 0$.

From Division Theorem: Positive Divisor, 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$:

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

Taking:

- $q = -\tilde q, r = \tilde r$

the existence has been proved of integers $q$ and $r$ 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$

## Proof 2

Consider the set of integer multiples $x \, \left|{b}\right|$ of $\left|{b}\right|$ less than or equal to $a$:

- $M := \left\{{k \in \Z: \exists x \in \Z: k = x \, \left|{b}\right|, k \le a}\right\}$

We have that:

- $- \left|{a}\right| \, \left|{b}\right| \le - \left|{a}\right| \le a$

and so $M \ne \varnothing$.

From Set of Integers Bounded Above by Integer has Greatest Element, $M$ has a greatest element $h \, \left|{b}\right|$.

Then $h \, \left|{b}\right| \le a$ and so:

- $a = h \, \left|{b}\right| + r$

where $r \ge 0$.

On the other hand:

- $\left({h + 1}\right) \, \left|{b}\right| = h \, \left|{b}\right| + \left|{b}\right| > h \, \left|{b}\right|$

So:

- $\left({h + 1}\right) \, \left|{b}\right| > a$

and:

- $h \, \left|{b}\right| + \left|{b}\right| > h \, \left|{b}\right| + r$

Thus:

- $r \le b$

Setting:

- $q = h$ when $b > 0$
- $q = -h$ when $b < 0$

it follows that:

- $h \, \left|{b}\right| = q b$

and so:

- $a = q b + r$

as required.

$\blacksquare$

## Informal Proof

### Existence

Consider the progression:

- $\ldots, a - 3 b, a - 2 b, a - b, a, a + b, a + 2 b, a + 3 b, \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 the progression.

### Uniqueness

Suppose 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 the solution is unique.

$\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**.

## Also see

## Sources

- 1968: Ian D. Macdonald:
*The Theory of Groups*... (previous) ... (next): Appendix: Elementary set and number theory - 1970: B. Hartley and T.O. Hawkes:
*Rings, Modules and Linear Algebra*... (previous) ... (next): $\S 2.3$: Some properties of subrings and ideals - 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 8.28$