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 \(n\) and \(d\) be integers. Then there exist unique integers \(q\) and \(r\) such that \(n=dq+r, 0\leq r <|d|\), where \(q\) is the quotient and \(r\) is the remainder, and the absolute value of \(d\) is defined as:

\[|d|= \left\{ \begin{array}{c}
d, \mbox{if } d \geq 0\\
\\
-d, \mbox{if } d<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\).