1.1: Division Algorithm

Example \(\PageIndex{1}\)

Suppose \(347\) objects are placed into groups of \(23\).

How many complete groups can be formed?
How many objects remain after forming the groups?

\begin{align*}
347 & =23(15)+2
\end{align*}
Here, \(347\) is the dividend, \(23\) is the divisor, \(15\) is the quotient and \(2\) is the remainder. Notice that \(0\leq 2<23\).

 

In proving numerous theorems, we will use the well-ordering principle.

Theorem \(\PageIndex{1}\): Well ordering principle

Every non-empty subset of \(\mathbb{N}\) has a smallest element.

Remember:

Let \(b\) be an integer. Then the absolute value of \(b\) is defined as:

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

 Division Algorithm

Below is the division algorithm for positive divisors.

Theorem \(\PageIndex{2}\): Division Algorithm I

Let \(a,b\in\mathbb{Z}\) with \(b>0\). Then there exist unique integers
\(q,r\in\mathbb{Z}\) such that
\begin{align*}
a=bq+r,
\qquad 0\leq r<b.
\end{align*}

The integer \(q\) is called the quotient, and \(r\) is called
the remainder.

Proof

Let \(a,b\in\mathbb{Z}\) with \(b>0\). 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 cases a & b are non-empty sets, \(S \ne \emptyset \subseteq \mathbb{N}\).

Thus, \(S\) has a smallest element by the well-ordering principle; let's 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 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 the fact 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 \mid (r_2-r_1)\), but
\(
|r_2-r_1|<|b|.
\)

The only multiple of \(b\) having absolute value less than \(|b|\)
is \(0\). Therefore,
\(
r_2-r_1=0,
\)

Hence \(q_1=q_2\).

Therefore, uniqueness has been shown.

 

Below is the division algorithm for non-zero divisors. 

Theorem \(\PageIndex{3}\) Division Algorithm II

Let \(a,b\in\mathbb{Z}\) with \(b\ne 0\). Then there exist unique integers
\(q,r\in\mathbb{Z}\) such that
\begin{align*}
a=bq+r,
\qquad 0\leq r< |b|.
\end{align*}

The integer \(q\) is called the quotient, and \(r\) is called
the remainder.

Proof

Let \(a,b\in\mathbb{Z}\). Assume  \(b<0\).

Since \(b<0\), we have \(-b>0\). Applying the Division Algorithm to the positive integer \(-b\), there exist unique integers \(q_0,r\) such that \( a=(-b)q_0+r, \qquad 0\leq r<-b. \) 

Since \( (-b)q_0=b(-q_0), \) we can write \( a=b(-q_0)+r. \) Let \( q=-q_0. \) Then \( a=bq+r. \)

Furthermore, since \(b<0\), \( |b|=-b. \) Thus \( 0\leq r<-b=|b|. \) Therefore, \( a=bq+r, \qquad 0\leq r<|b|. \)

It remains to prove uniqueness. Suppose \( a=bq_1+r_1=bq_2+r_2, \) where \( 0\leq r_1<|b| \qquad\text{and}\qquad 0\leq r_2<|b|. \) Then \( b(q_1-q_2)=r_2-r_1. \) Hence \(b\mid(r_2-r_1)\).

Also, \( -|b|<r_2-r_1<|b|. \) The only multiple of \(b\) whose absolute value is less than \(|b|\) is \(0\).

Therefore, \( r_2-r_1=0, \) so \( r_1=r_2. \) It follows that \( b(q_1-q_2)=0. \) Since \(b\neq0\), \( q_1=q_2. \) Hence \(q\) and \(r\) are unique. Therefore, for every \(a,b\in\mathbb{Z}\) with \(b\neq0\), there exist unique integers \(q,r\in\mathbb{Z}\) such that \( a=bq+r,\qquad 0\leq r<|b|. \)

Definition: 

In the equation \( a=bq+r, \) the terms have the following meanings:

\( \begin{array}{c|l} \textbf{Term} & \textbf{Meaning}\\ \hline a & \text{Dividend}\\ b & \text{Divisor}\\ q & \text{Quotient}\\ r & \text{Remainder} \end{array} \)

Example \(\PageIndex{2}\)

For \(a=-47, b=6: -47=6(-8)+1\). For \(a=47, b=-6: 47=(-6)(-7)+5\). For \(a=-47, b=-6: -47=(-6)(8)+1\).

Caution

The remainder must satisfy

\(0\leq r<|b|.\)

In particular, the remainder is never negative.

Example \(\PageIndex{3}\)

Find \(q\), the quotient, and \(r\), the remainder, for the following values of \(n\) and \(d\).

1. \(n=2018\) and \(d=343\).

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

Example \(\PageIndex{4}\): Negative dividend

Find \(q\) and \(r\) such that
\begin{equation*}
-347=23q+r,
\qquad
0\leq r<23.
\end{equation*}

We have
\begin{equation*}
-347=23(-16)+21.
\end{equation*}

Therefore,
\begin{equation*}
\boxed{q=-16,\qquad r=21.}
\end{equation*}

Caution: Common error

The expression
\begin{equation*}
-347=23(-15)-2
\end{equation*}
is algebraically correct, but it is not in Division Algorithm form because the remainder is negative.

The remainder must satisfy
\begin{equation*}
0\leq r<|b|.
\end{equation*}
 

Example \(\PageIndex{5}\): Negative divisor

Find \(q\) and \(r\) such that
\begin{equation*}
347=(-23)q+r,
\qquad
0\leq r<23.
\end{equation*}

Since
\begin{equation*}
347=(-23)(-15)+2,
\end{equation*}
we obtain
\begin{equation*}
\boxed{q=-15,\qquad r=2.}
\end{equation*}

Note

When the divisor \(b\) is negative, the remainder condition still uses
\begin{equation*}
|b|.
\end{equation*}

Thus
\begin{equation*}
0\leq r<|b|.
\end{equation*}

Example \(\PageIndex{6}\): Negative dividend and negative divisor

Find \(q\) and \(r\) such that
\begin{equation*}
(-347)=(-23)q+r,
\qquad
0\leq r<23.
\end{equation*}

Since
\begin{equation*}
(-347)=(-23)(16)+21,
\end{equation*}
we obtain
\begin{equation*}
\boxed{q=16,\qquad r=21}
\end{equation*}