§1.1 The Division Algorithm

Well-Ordering Axiom

Our starting point is the set of all integers $\mathbb{Z} = \{0, \pm 1, \pm 2, \dots\}$. We assume that you are familiar with the arithmetic of integers and with the usual order relation $(<)$ on the set $\mathbb{Z}$. We also assume the...

The Well-Ordering Axiom: Every nonempty set of nonnegative integers contains a smallest element.

If you think of the nonnegative integers laid out on the usual number line, it is intuitively plausible that each subset contains an element that lies to the left of all the other elements in the subset—that is the smallest element. On the other hand, the Well-Ordering Axiom does not hold in the set $\mathbb{Z}$ of all integers (there is no smallest negative integer). Nor does it hold in the set of all nonnegative rational numbers (the subset of all positive rationals does not contain a smallest element because, for any positive rational number $r$, there is always a smaller positive rational—for instance, $r/2$).

Introducing the Division Algorithm

So here we go. Consider the following grade-school division problem:

$$ \begin{array}{c|c} \text{Quotient} & 11 \\ \text{Divisor} & 7 \\ \text{Dividend} & 82 \\ \text{Remainder} & 5 \\ \end{array} $$

$$ \begin{array}{c} \text{Check:} \\ 11 \times 7 \quad \text{Quotient} \\ 77 \quad \text{Divisor} \\ +5 \quad \text{Remainder} \\ 82 \quad \text{Dividend} \\ \end{array} $$

The division process stops when we reach a remainder that is less than the divisor. All the essential facts are contained in the checking procedure, which may be verbally summarized like this:

$$ \text{dividend} = (\text{divisor})(\text{quotient}) + (\text{remainder}). $$

Here is a formal statement of this idea, in which the dividend is denoted by $a$, the divisor by $b$, the quotient by $q$, and the remainder by $r$:

Theorem 1.1: The Division Algorithm

Let $a, b$ be integers with $b > 0$. Then there exist unique integers $q$ and $r$ such that $$ a = bq + r \quad \text{and} \quad 0 \leq r < b. $$

Theorem 1.1 allows the possibility that the dividend $a$ might be negative but requires that the remainder $r$ must not only be less than the divisor $b$ but also must be nonnegative. To see why this last requirement is necessary, suppose $a = -14$ is divided by $b = 3$, so that $-14 = 3q + r$. If we only require that the remainder be less than the divisor 3, then there are many possibilities for the quotient $q$ and remainder $r$, including these three:

$$ -14 = 3(-3) + (-5), \quad \text{with} -5 < 3 \quad \text{[Here } q = -3 \text{ and } r = -5.] $$

$$ -14 = 3(-4) + (-2), \quad \text{with} -2 < 3 \quad \text{[Here } q = -4 \text{ and } r = -2.] $$

$$ -14 = 3(-5) + 1, \quad \text{with} 1 < 3 \quad \text{[Here } q = -5 \text{ and } r = 1.] $$

When the remainder is also required to be nonnegative as in Theorem 1.1, then there is exactly one quotient $q$ and one remainder $r$, namely, $q = -5$ and $r = 1$, as will be shown in the proof.

The fundamental idea underlying the proof of Theorem 1.1 is that division is just repeated subtraction. For example, the division of 82 by 7 is just a shorthand method for repeatedly subtracting 7:

$$ \begin{aligned} 82 - 7 &= 75 \quad &82 - 7 \cdot 1 &= 75 \\ 75 - 7 &= 68 \quad &82 - 7 \cdot 2 &= 68 \\ 68 - 7 &= 61 \quad &82 - 7 \cdot 3 &= 61 \\ 61 - 7 &= 54 \quad &82 - 7 \cdot 4 &= 54 \\ 54 - 7 &= 47 \quad &82 - 7 \cdot 5 &= 47 \\ 47 - 7 &= 40 \quad &82 - 7 \cdot 6 &= 40 \\ 40 - 7 &= 33 \quad &82 - 7 \cdot 7 &= 33 \\ 33 - 7 &= 26 \quad &82 - 7 \cdot 8 &= 26 \\ 26 - 7 &= 19 \quad &82 - 7 \cdot 9 &= 19 \\ 19 - 7 &= 12 \quad &82 - 7 \cdot 10 &= 12 \\ 12 - 7 &= 5 \quad &82 - 7 \cdot 11 &= 5 \\ \end{aligned} $$

The subtractions continue until you reach a nonnegative number less than 7 (in this case 5). The number 5 is the remainder, and the number of multiples of 7 that were subtracted (namely, 11, as shown at the right of the subtractions) is the quotient.

In the preceding example we looked at the numbers $82 - 7x$ for $x = 1, 2, 3, \dots$, and found the smallest nonnegative one (namely, 5). In the proof of Theorem 1.1 we shall do something very similar.

Step-by-Step Proof: The Divisional Algorithm

Let $a$ and $b$ be fixed integers with $b > 0$. Consider the set $S$ of all integers of the form $$ a - bx, $$ where $x$ is an integer and $a - bx \geq 0$.

Note that $x$ may be any integer—positive, negative, or 0—but $a - bx$ must be nonnegative. There are four main steps in the proof, as indicated below.

Step 1

Show that $S$ is nonempty by finding a value for $x$ such that $a - bx \geq 0$.

Proof of Step 1: We first show that $a + b|a| \geq 0$. Since $b$ is a positive integer by hypothesis, we must have

$$ b \geq 1 $$ $$ b|a| \geq |a| $$ $$ b|a| \geq -a \quad \text{[Multiply both sides of the preceding inequality by } |a|]. $$ $$ a + b|a| \geq 0. \quad \text{[Because } |a| \geq -a \text{ by the definition of absolute value.]} $$

Now let $x = -|a|$. Then $$ a - bx = a - b(-|a|) = a + b|a| \geq 0. $$ Hence, $a - bx$ is in $S$ when $x = -|a|$, which means that $S$ is nonempty.

Step 2

Find $q$ and $r$ such that $a = bq + r$ and $r \geq 0$.

Proof of Step 2: By the Well-Ordering Axiom, $S$ contains a smallest element—call it $r$. Since $r \in S$, we know that $r \geq 0$ and $r = a - bx$ for some $x$, say $x = q$. Thus,

$$ r = a - bq \quad \text{and} \quad r \geq 0, \quad \text{or, equivalently,} \quad a = bq + r \quad \text{and} \quad r \geq 0. $$

Step 3

Show that $r < b$.

Proof of Step 3: We shall use a "proof by contradiction" (which is explained on page 506 of Appendix A). We want to show that $r < b$. So suppose, on the contrary, that $r \geq b$. Then $r - b \geq 0$, so that

$$ 0 \leq r - b = (a - bq) - b = a - b(q + 1). $$ Since $a - b(q + 1)$ is nonnegative, it is an element of $S$ by definition. But since $b$ is positive, it is certainly true that $r - b < r$. Thus,

$$ a - b(q + 1) = r - b < r. $$ The last inequality states that $a - b(q + 1) = r - b$—which is an element of $S$—is less than $r$, the smallest element of $S$. This is a contradiction. So our assumption that $r \geq b$ is false, and we conclude that $r < b$. Therefore, we have found integers $q$ and $r$ such that

$$ a = bq + r \quad \text{and} \quad 0 \leq r < b. $$

Step 4

Show that $r$ and $q$ are the only numbers with these properties (that's what "unique" means in the statement of the theorem).

Proof of Step 4: To prove uniqueness, we suppose that there are integers $q_1$ and $r_1$ such that $a = bq_1 + r_1$ and $0 \leq r_1 < b$, and prove that $q_1 = q$ and $r_1 = r$.

Since $a = bq + r$ and $a = bq_1 + r_1$, we have $$ b(q - q_1) = r_1 - r. $$ Furthermore, $$ 0 \leq r < b $$ $$ 0 \leq r_1 < b. $$ Multiplying the first inequality by $-1$ (and reversing the direction of the inequality), we obtain $$ -b < r_1 - r \leq 0 $$ $$ 0 \leq r_1 < b. $$ Adding these two inequalities produces $$ -b < r_1 - r < b $$ $$ -b < b(q - q_1) < b \quad \text{[By Equation (*)]} $$ $$ -1 < q - q_1 < 1 \quad \text{[Divide each term by } b. \text{]} $$ But $q - q_1$ is an integer (because $q$ and $q_1$ are integers) and the only integer strictly between $-1$ and 1 is 0. Therefore $q - q_1 = 0$ and $q = q_1$. Substituting $q - q_1 = 0$ in Equation (*) shows that $r_1 - r = 0$ and hence $r = r_1$. Thus the quotient and remainder are unique, and the proof is complete. $\blacksquare$

When both the dividend $a$ and the divisor $b$ in a division problem are positive, then the quotient and remainder are easily found either by long division or with a calculator when the integers involved are larger.

Example 1.1.1: Division with Positive Integers

Suppose $a = 4327$ is divided by $b = 281$. Entering $a/b$ in a calculator produces 15.39857... The integer to the left of the decimal point (15 here) is the quotient $q$ and the remainder is $$ r = a - bq = 4327 - 281 \cdot 15 = 112. $$ When the dividend $a$ is negative, a slightly different procedure is needed so that the remainder will be nonnegative.

Example 1.1.2: Division with Negative Dividend

Suppose $a = -7432$ is divided by $b = 453$. Entering $a/b$ in a calculator produces $-16.40618\ldots$. In this case, the quotient $q$ is not $-16$; instead, $$ q = (\text{the integer to the left of the decimal point}) - 1 = -16 - 1 = -17. $$ (Without this adjustment, you will end up with a negative remainder.) Now, as usual, $$ r = a - bq = -7432 - 453 \cdot (-17) = 269. $$