1.5: The Division Algorithm

The goal of this section is to prove the following important result.

Theorem \(\PageIndex{1}\): The Division Algorithm

If \(a\) and \(b\) are integers and \(b>0\) then there exist unique integers \(q\) and \(r\) satisfying the two conditions: \[\label{eq:1}a=bq+r\quad\text{and}\quad 0\leq r<b.\]

In this situation \(q\) is called the quotient and \(r\) is called the remainder when \(a\) is divided by \(b\). Note that there are two parts to this result. One part is the EXISTENCE of integers \(q\) and \(r\) satisfying \(\eqref{eq:1}\) and the second part is the UNIQUENESS of the integers \(q\) and \(r\) satisfying \(\eqref{eq:1}\)

Proof

Given \(b > 0\) and any \(a\) define \[\begin{aligned} q &=& \left \lfloor \frac ab \right \rfloor \\ r &=& a - bq\end{aligned}\] Cleary we have \(a = bq + r\). But we need to prove that \(0\le r<b\). By Lemma 4.1 we have \[\frac ab-1<\left\lfloor\frac ab\right\rfloor\le\frac ab.\nonumber \] Now multiply all terms of this inequality by \(-b\). Since \(b\) is positive, \(-b\) is negative so the direction of the inequality is reversed, giving us: \[b-a >-b \left \lfloor \frac ab \right \rfloor \ge -a.\nonumber \] If we add \(a\) to all sides of the inequality and replace \({\mbox{$ \lfloor a/b \rfloor $}}\) by \(q\) we obtain \[b > a-bq \ge 0.\nonumber \] Since \(r=a-bq\) this gives us the desired result \(0\le r<b\).

We still have to prove that \(q\) and \(r\) are uniquely determined. To do this we assume that \[a=bq_1+r_1\quad\text{and}\quad 0\le r_1<b,\nonumber \] and \[a=bq_2+r_2\quad\text{and}\quad 0\le r_2<b.\nonumber \] We must show that \(r_1=r_2\) and \(q_1=q_2\). If \(r_1\neq r_2\) without loss of generality we can assume that \(r_2>r_1\). Subtracting these two equations we obtain \[0=a-a=(bq_1+r_1)-(bq_2+r_2)=b(q_1-q_2)+(r_1-r_2).\nonumber \] This implies that \[\label{eq:2} r_2-r_1 = b(q_1-q_2).\] This implies that \(b\mid r_2-r_1\). By Theorem 3.1(10) this implies that \(b\le r_2-r_1\). But since \[0 \le r_1 < r_2 < b\nonumber \] we have \(r_2-r_1<b\). This contradicts \(b\le r_2-r_1\). So we must conclude that \(r_1=r_2\). Now from \(\eqref{eq:2}\) we have \(0=b(q_1-q_2)\). Since \(b>0\) this tells us that \(q_1-q_2=0\), that is, \(q_1=q_2\). This completes the proof of the uniqueness of \(r\) and \(q\) in \(\eqref{eq:1}\)

Definition \(\PageIndex{1}\)

An integer \(n\) is even if \(n=2k\) for some \(k\), and is odd if \(n=2k+1\) for some \(k\).

Exercise \(\PageIndex{1}\)

Prove using the Division Algorithm that every integer is either even or odd, but never both.

Definition \(\PageIndex{2}\)

By the parity of an integer we mean whether it is even or odd.

Exercise \(\PageIndex{2}\)

Prove \(n\) and \(n^2\) always have the same parity. That is, \(n\) is even if and only if \(n^2\) is even.

Exercise \(\PageIndex{3}\)

Find the \(q\) and \(r\) of the Division Algorithm for the following values of \(a\) and \(b\):

1. Let \(b=3\) and \(a=0,1,-1,10,-10\).
2. Let \(b=345\) and \(a=0,-1,1,344,7863,-7863\).

Exercise \(\PageIndex{4}\)

Devise a method for solving problems like those in the previous exercise for large positive values of \(a\) and \(b\) using a calculator. Illustrate by using \(a=123456\) and \(b=123\).

Hint

If \(a=bq+r\) and \(0\le r<b\) then \(\frac ab=q+\frac rb\) and so \(\frac rb\) is the fractional part of the decimal number \(\frac ab\). So \(q\) is what you get when you drop the fractional part. Once you have \(q\) you can solve \(a=bq+r\) for \(r\).

Sometimes a problem in number theory can be solved by dividing the integers into various classes depending on their remainders when divided by some number \(b\). For example, this is helpful in solving the following two problems.

Exercise \(\PageIndex{5}\)

Show that for all integers \(n\) the number \(n^3-n\) always has 3 as a factor. (Consider the three cases: \(n=3k\), \(n=3k+1\), \(n=3k+2\).)

Exercise \(\PageIndex{6}\)

Show that the product of any three consecutive integers has 6 as a factor. (How many cases should you use here?)

Definition \(\PageIndex{3}\)

For \(b>0\) define \(a\bmod b=r\) where \(r\) is the remainder given by the Division Algorithm when \(a\) is divided by \(b\), that is, \(a=bq+r\) and \(0\le r<b\).

For example \(23\bmod 7=2\) since \(23=7\cdot 3+2\) and \(-4\bmod 5=1\) since \(-4=5\cdot (-1)+1\).

Note that some calculators and most programming languages have a function often denoted by \(MOD(a,b)\) or \(mod(a,b)\) whose value is what we have just defined as \(a\bmod b\). When this is the case the values \(r\) and \(q\) in the Division Algorithm for given \(a\) and \(b>0\) are given by \[\begin{aligned} r &=a \bmod b \\ q &=\frac{a-(a \bmod b)}{b}\end{aligned}\] If also the floor function is available we have \[\begin{aligned} r &=a \bmod b \\ q &=\left \lfloor a/b \right \rfloor\end{aligned}\]

Exercise \(\PageIndex{7}\)

Prove that if \(b>0\) then \(b \mid a\iff a \bmod b=0\).

Exercise \(\PageIndex{8}\)

Prove that if \(b \neq 0\) then \(b\mid a\Longleftrightarrow a/b\in\mathbb{Z}\).

Exercise \(\PageIndex{9}\)

Calculate the following:

1. \(0\bmod 10\)
2. \(123\bmod 10\)
3. \(10\bmod 123\)
4. \(457\bmod 33\)
5. \((-7) \bmod 3\)
6. \((-3) \bmod 7\)
7. \((-5) \bmod 5\)

Exercise \(\PageIndex{10}\)

Use the Division Algorithm to prove the following more general version: If \(b\neq 0\) then for any \(a\) there exists unique \(q\) and \(r\) such that \[\label{eq:3} a=bq+ r\quad\text{and}\quad 0\le r < |\, b \,|. \]

Hint

Recall that \(|\,b\,|\) is \(b\) if \(b\ge 0\) and is \(-b\) if \(b<0\). We know the statement holds if \(b>0\) so we only need to consider the case when \(b<0\). If \(b\) is negative then \(-b\) is positive, so we can apply the Division Algorithm to \(a\) and \(-b\). Note that \(a\) as well as \(q\) can be any integers. This exercise may come in handy later.