Division Algorithm

Set of Integers

We begin the class by discussing the most familiar algebraic operation on the set of integers. We denote the set of integers by:

$$\mathbb{Z}=\{\dots ,-3,-2,-1,0,1,2,3,\dots \}.$$

We denote the set of positive integers by:

$${\mathbb{Z}}_{+}=\{1,2,3,\dots \}.$$

We denote the set of nonnegative integers by:

$${\mathbb{Z}}_{\ge 0}=\{0,1,2,3,\dots \}.$$

The notations for the set of negative, nonpositive, and nonnegative integers are similar.

Classical Division

In grade school, we learned how to divide numbers. For example:

$$\begin{array}{rl}82÷7& =11+5.\end{array}$$

Or equalvalently:

$$\begin{array}{rl}82& =11\times 7+5.\end{array}$$

Verbally, we say “82 divided by 7 equals 11 with a remainder of 5.” We will refer the 82 to be the dividend, the 7 to be the divisor, the 11 to be the quotient, and the 5 to be the remainder. The division we learned can be verbally stated as:

$$\begin{array}{rl}\text{Dividend}& =\text{Quotient}\times \text{Divisor}+\text{Remainder}.\end{array}$$

One may say we arrange different numbers in a way that the above equation holds. For example:

$$\begin{array}{rl}82& =11\times 7+5,\\ & =10\times 7+16,\\ & =12\times 7+(-2).\end{array}$$

Remainder Condition

And seemingly we have amgibuity in the quotient and the remainder. However, as we actually learned in grade school, the quotient and the remainder are unique, as long as we require the following Remainder Condition:

$$\begin{array}{r}0\le \text{Remainder}<|\text{Divisor}|.\end{array}$$

Division Algorithm Theorem

We will state the existence and uniqueness of the quotient and the remainder as a theorem, for simplicity, we will assume the divisor is positive. The theorem is stated as follows:

Theorem

Let $a,b$ be integers with $b>0$. Then there exist unique integers $q$ and $r$ such that:

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

The theorem has two parts: existence and uniqueness. The existence part ensure we can always find a quotient and a remainder that satisfy the equation. The uniqueness part ensure the quotient and the remainder are unique. The proof idea can be summarized as follows:

Proof Idea

Find the minimal positive remainder that satisfy the equation. Then show that the remainder must be unique.

Well-Ordering Axiom

To make the idea works, we need the standard Well-Ordering Axiom:

Well-Ordering Axiom

Every nonempty subset of ${\mathbb{Z}}_{\ge 0}$ has a smallest element.

The Well-Ordering Axiom is something that we take for granted. One could say it follows from Zorn’s Lemma, but again, Zorn’s Lemma is something people take for granted.

Click Proof of the Division Algorithm to see the proof of the theorem.