[Math Talk #24] Integer Division Algorithm

We all know how to obtain quotients and remainder using the division algorithm for integers. But why is it always possible to have a unique pair of quotient and remainder? This stems from the well ordering principle.

Well Ordering Principle

The precise proof of existence and uniqueness of quotient and remainder in the division algorithm heavily relies on well ordering principle. Well ordering principle comes from axiomatic set theory, so to make long story short, it states that any non-empty subset of natural numbers (= non-negative integers) contains a least element.

Well Ordering Principle. Every nonempty subset $S \subseteq \mathbb{N}$ contains an integer $a \in S$ such that $a \leq b$ for all $b$ 's belonging to $S$ .

In fact, there are several ways to construct Natural numbers. If you follow Peano arithmetic, then Well ordering principle is a direct consequence of principle of mathematical induction. On the other hand, if you follow axiomatic set theory; natural numbers are the smallest inductive set, then well ordering principle becomes trivial by construction itself. In either case, it is a fundamental fact, so do not try to find counterexamples...

Well known Division algorithm

The integer division algorithm can be summarized as follows.

Integer Division Algorithm. Given two integers $a,b$ , with $b \neq 0$ , there exist unique integers $q$ and $r$ satisfying

$a = qb + r$ with
$0 \leq r < |b|$
We call $q$ as the quotient, $r$ as the remainder.

For example, for two integers $37$ and $8$ , we have relation

$37=4\times 8+5$

so that $q=4, r=5$ . Another example involving negative integers would be $a=-37, b=-4$ , then the relation becomes

$-37=10 \times (-4) + 3$

so that $q=10,\ r=3$ . We can clearly see that in integer division algorithm, quotient and remainder is unique.

Why do they exist?

Well ordering principle can give us a lot of help in proving existence. For given two integers $a,b$ with $b\neq0$ , construct a subset of natural numbers

$S= \left\{ a - xb : x \text{ is an integer and } a-xb \geq 0 \right\}$

In order to use well ordering principle, we must show that $S$ is nonempty. If $b$ is positive, we need some negative integer $x$ satisfying $a-xb \geq 0$ . A good guess would be $-|a|$ . In fact,

$a-(-|a|)b = a + |a|b \geq a + |a| \geq 0$

makes $S$ nonempty. Also, if $b$ is negative, $|a|$ will give us a desired result. Either case S is nonempty, so the set $S$ contains a smllest element, namely $r$ using well ordering principle. By definition of $S$ , there exist an integer $q$ such that

$a-qb = r \iff a = qb + r$

Are we done? Not yet. We must show that $r < |b|$ . Here we use the method of contradiction assuming $r \geq |b|$ .

Assume $b > 0$ . Then $a - (q+1)b = r - b \geq 0$ so that $r-b \in S$ . However, this contradicts to the choice of $r$ as the smallest element of $S$ .
Assume $b < 0$ . Then

$a - (q-1)b = r+b \geq |b|+b \geq 0$

so that $r + b \in S$ . Again this leads to contradiction. Thus $r < |b|$ .

Why are they unique?

Technically, showing uniqueness is easy. Suppose there are two different pairs of quotient and remiander.

$a = q_1b + r_1 = q_2b + r_2$

. Then

$r_1 - r_2 = b(q_2 - q_1) \implies |r_1 - r_2| = |b| \cdot |q_2 - q_1|$

Since both $r_1, r_2$ satisfy $0 \leq r_i < |b|$ , the difference should be less than $|b|$ . Therefore, $|r_1 - r_2| = |b| \cdot |q_1 - q_2| < |b|$ leads to

$|q_1 - q_2| < 1$

Because $q_1 - q_2$ is an integer, the only possibility is $q_1 - q_2 = 0$ , whence $q_1 = q_2$ . From this, we get $r_1 = r_2$ , ending the proof of uniqueness.

Extension to any real number

The division algorithm of integers can be easily extended to division involving two real numbers. For two real numbers $x, y$ with $y \neq 0$ , there always exist a quotient $q$ and remainder $r$ such that

$x= qy + r$
$0 \leq r < |y|$

Note that quotient is an integer but remainder isn't.

If we fix a nonzero real number $y$ as 1, then we can partition the set of real numbers by equivalence classes

$[x] = \left\{ s \in \mathbb{R} : x \text{ and }s \text{ have same remainder} \right\}$

This is equivalent to saying that any equivalence class has 1-1 correspondance with unit interval $[0, 1)$ by

$[x] \mapsto r_x,\ (r_x \text{ is remainder when divided by 1})$

If you are familiar with quotient groups, what we've constructed is a quotient group

$\mathbb{R}/\mathbb{Z}$

. With a continuous function $f(r_x) = (\cos(2\pi r_x), \sin(2\pi r_x))$ defined on unit interval [0, 1), this group can be viewed as a unit circle on a 2D plane.

Conclusion

Well Ordering principle helps us to prove the existence of quotient and remainder in integer division algorithm.
In fact, quotient and remainder are unique.
We can extend this division algorithm to real numbers. Furthermore, each equivalence class of remainder corresponds to unique point in unit interval [0, 1).
This can be viewed as another way of representing unit circle.

Notable sources

Elementary number theory - David M.Burton Chapter 2, Section 1.

Congratulations! This post has been upvoted from the communal account, @minnowsupport, by Mathsolver from the Minnow Support Project. It's a witness project run by aggroed, ausbitbank, teamsteem, someguy123, neoxian, followbtcnews, and netuoso. The goal is to help Steemit grow by supporting Minnows. Please find us at the Peace, Abundance, and Liberty Network (PALnet) Discord Channel. It's a completely public and open space to all members of the Steemit community who voluntarily choose to be there.

If you would like to delegate to the Minnow Support Project you can do so by clicking on the following links: 50SP, 100SP, 250SP, 500SP, 1000SP, 5000SP.
Be sure to leave at least 50SP undelegated on your account.

Sort:

Trending

[-]

minnowsupport (71) 6 years ago