2.6: Division Algorithm

The absolute value

Definition: Absolute value

For any real number \(x\) the absolute value of \(x\) is denoted by \(|x|\) and defined by
\[|x|= \left\{\begin{array}{cc}
x& \mbox{ if } x\geq 0,\\
-x& \mbox{ if } x< 0.
\end{array}
\right.\]

Example \(\PageIndex{1}\) : Absolute Value

Consequently we see that \(|-2|=|2|=2.\)

Example \(\PageIndex{2}\)

Consider the simple example of dividing \(7\) by \(2\):
\begin{align*}
7 &= 2(3)+1.
\end{align*}
Here, \(3\) is the quotient and \(1\) is the remainder. Notice that \(0\leq 1<2\).

 To prove the division algorithm, we will utilize the well-ordering principle.

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

Every non-empty subset of \(\bf N\) has a smallest element.

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

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 that they 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 \cap 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|(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.

Theorem \(\PageIndex{2}\)

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|. \)

 

 

Example \(\PageIndex{3}\): Positive Dividend

1. Find the quotient and remainder when \(2018\) is divided by \(343\).

Since
\begin{equation*}
2018=343(5)+303,
\end{equation*}
we obtain
\begin{equation*}
q=5,\qquad r=303.
\end{equation*}

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

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

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

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

 

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*}

 Now we are ready to solve some word problems:

Example \(\PageIndex{7}\):

Today is March 3, 2018, and it is Friday. What day of the week will March 3, 2019, fall on?

At first, note that 2019 is not a leap year. Therefore, there are \(365\) days between March 3, 2018, and March 3, 2019. Also \(365=(52)(7)+1\). There are seven days in a week, and if we set Friday as 0, then March 3, 2019, will be a Saturday.

Leap Year

The Gregorian calendar is the calendar we most commonly use today worldwide. The Gregorian calendar consists of both common years with 365 days and Leap years with 366 days, due to the intercalary day added on February 29th. Leap years are necessary to keep the Gregorian calendar aligned with the Earth’s revolution around the Sun.

 

Following our modern-day Gregorian calendar, there are three rules to take into consideration to identify leap years:

1. The year must be evenly divisible by 4.
2. If the year is evenly divisible by 100, it is not a leap year unless:
3. The year is also evenly divisible by 400.

For example, the years 1600, 1800, and 2000 are all leap years, but the years 1700 and 1900 aren’t.

Example \(\PageIndex{8}\):

Each day, Ms. Mary visits grocery stores A, B, C, D in that order. Further, she spends exactly \( \$ 27, \$ 35, \$ 12, \$ 40\) in stores A, B, C, and D, respectively. Her total expenditure from the beginning of the month up to a certain day was \(\$924\). Which store would she be visiting next?

Example \(\PageIndex{9}\)

In a 101-digit number that is a multiple of 13, the first 50 digits are all 5s, and the last 50 digits are all 8s. What is the middle digit?

Solution

Since \( 13 | 555555 \) and \( 13 | 888888,\) we need to consider what the value of \( X \in ℤ\) is such that \(13 | 55X88 \), since
the first and last \(48\) digits of the number will produce multiples of \(13. \) At this point (Solution 1), trial and error can be applied to this calculation, resulting in X = 5.

A more elegant solution (Solution 2) can be obtained by recognizing that any number \( Q ∈ ℤ+ \) can be written as:

\( Q = 10a + b, \) where \( a, b ∈ \{0, 1, ..., 8, 9\}. \)

Next, find a multiple of \(13\) that has a \(1 \) as the last digit. This condition is satisfied with \(91\). Next, rewrite the equation to be \(Q - 91b = 10a + b - 91b \) and simplify to \(Q - 91b = 10(a - 9b). \) Using this formula, \(55X8 - 9(8)\) a number whose last digit is a \(6\), is divisible by \(13 \) and the first two digits must be either \(55 \) or \(54 \) will satisfy the condition \( 13 | 55X88.\) The only number that satisfies these conditions is \(5486. \) Adding back \(72,\) we obtain \(5558,\) thus confirming that \(X = 5.\)

A more deductive solution (Solution 3) can be seen using long division as follows: