1.1: Division Algorithm

In the proof of numerous theorems, we will utilize the well-ordering principle.

Theorem $\PageIndex{1}$: Well ordering principle

Every non-empty subset of $\mathbb{N}$ has the smallest number.

 Division Algorithm

Theorem $\PageIndex{2}$: Division Algorithm

Let $a$ and $b \ne 0$ be integers. Then there exist unique integers $q$ and $r$ such that $a=bq+r, 0\leq r <|b|$, where $q$ is the quotient and $r$ is the remainder, and the absolute value of $d$ is defined as:

$$|b|= \left\{ \begin{array}{c} b, \mbox{if } b \geq 0\\ \\ -b, \mbox{if } b<0. \end{array} \right.$$

Proof

We will show that $q,r \in \mathbb{Z}$ exist and are unique.

Let $a,b \in \mathbb{Z}$ s.t. $b>0$.

Let $S$ be a set defined by  $S=\{a-bm: a-bm \ge 0, m\in \mathbb{Z}\}$.

We will show existence by examining the possible cases.

Case 1:  $0 \in S$

If $0 \in S$, then $a-bm=0$ for some $m \in \mathbb{Z}$.

Thus, $a=bm$

Since $b|a$, $q=m$ and $r=0$.

Therefore existence has been proved.

Case 2:  $0 \notin S$.

Since $0 \notin S$, we will show that $S \ne \emptyset$ by examining the possible cases.  Note: $S \subseteq \mathbb{N}$.

 

Case a:  $a>0$.

Since $a>0$, $a=a-b(0)>0$.

Therefore $a \in S$.

Case b: $a<0$.

Consider $a-bm$, where $m=2a$.

Thus $a-b(2a)=a(1-2b)$.

Consider  $1-2b$ is always negative since $b>0, b \in \mathbb{N}$, thus greatest $1-2b$ can be in $-1$.

Therefore $a(1-2b) \ge 0$ since $b \ge 1$.

Note: The $\ge$ could be > without loss of generality.

Since both case a & b are non-empty sets, $S \ne \emptyset \subseteq \mathbb{N}$.

Thus $S$ has the smallest element by the well-ordering principle, and lets call it $r$.  

That means $r=a-bm$, for some $m\in \mathbb{Z}$ where $r \ge 0$.

Thus the non-empty set is $r=a-bm \ge 0$.

 

We shall show that $r < b$ by proceeding with a proof by contradiction.

Assume that $r \ge b$.

Then $a-b(m+1)=a-bm-b=r-b \ge 0$ for some $m \in \mathbb{Z}$.

Then $r-b \in S$ and $r-b<r$. Note $(b>0)$

This contradicts that $r$ is the smallest element of $S$.

Therefore $r < b$.

Having examined all possible cases, $a=bq+r, 0 \le r < b$ exists.

Next, we will show uniqueness.

Let $r_1,r_2, q_1,q_2$ s.t. $a=bq_1+r_1$ and $a=bq_2+r_2$ with $0 \le r_1,r_2 < b$.

Consider $bq_1+r_1=bq_2+r_2$, $0 \le r_1<b$.

Further since $b(q_1-q_2)=r_2-r_1$, $b|(r_2-r_1)$, but $b$ has to be $\le r_1$.

Since, $r_2-r_1 < b$, $r_2-r_1=0$ and $r_1=r_2$.

Hence $q_1=q_2$.

Therefore uniqueness has been shown.

Example $\PageIndex{1}$

Find the $q$ is the quotient and $r$ is the remainder for the following values of $n$ and $d$.

1. $n=2018$ and $d=343$.

Thus $2018=(5)(343)+303$.

2. $n=-2018$ and $d=343$.

Thus $-2018=(-6)(343)+40$.

3, . $n=2018$ and $d=-343$.

Thus $2018=(6)(-343)+40$.

4.

$n=-2018$ and $d=-343$.

Thus $-2018=(6)(-343)+ 40$.