1.5: The Division Algorithm

The goal of this chapter is to introduce and 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{divalg} a=bq+r\quad\text{and}\quad 0\le r<b. \]

In this situation \(q\) is called the quotient and \(r\) is called the remainder when \(a\) is divided by \(b\). We sometimes refer to \(a\) as the dividend and \(b\) as the divisor.

(Some care must be taken with this last term, in light of how the divisor of an integer was defined in Section 1.4. It is correct both to say that 2 is not a divisor of 7, since \(2 \nmid 7\), though 2 is the divisor when 7 is divided by 2, yielding \(7 = 2\cdot 3 + 1\). Context should make it clear which meaning is intended.)

Note that there are two parts to the Division Algorithm’s statement. One part is the existence of integers \(q\) and \(r\) satisfying \(\eqref{divalg}\), and the second part is the uniqueness of the integers \(q\) and \(r\) satisfying \(\eqref{divalg}\).

Proof

We first prove the existence of \(q\) and \(r\).

If \(b\) divides \(a\) then \(a=kb\) for some integer \(k\), and we may write \(q=k\) and \(r=0\).

Suppose instead that \(b\) does not divide \(a\), and consider the collection \[\dots, \; a-3b, \; a-2b, \; a-b, \; a, \; a+b, \; a+2b, \; a+3b, \; \dots\nonumber \] of integers. Let \(S\) be the set of all these numbers that are non-negative. In symbols, \[S = \{a-kb \mid k \in \mathbb{Z}\, \text{ and }\, a-kb\geq 0\}.\nonumber \]

The set \(S\) is non-empty, since by the Archimedean Property there exists a natural number \(n\) such that \(n>-a\) and so \(nb \geq n > -a\) and hence \(a-(-n)b > 0\). Now by the Well-Ordering Principle \(S\) contains a smallest element; call it \(r\). By our definition of \(S\), this means that for some particular integer \(q\) we have \(r=a-qb\). Thus \(a = bq+r\), and it only remains to show that \(0 \leq r < b\).

All the elements of \(S\) are positive, so it is clear that \(0 \leq r\). If it is not true that \(r < b\), then \(a-bq \geq b\) and so \(r-b = a-(q+1)b \geq 0\); thus either \(r-b\) is an element of \(S\) or \(r-b=0\). Since \(r\) was defined as the smallest element of \(S\), it cannot be true that \(r-b\) is in \(S\). However, if \(r-b=0\), then \(a = bq+b = (q+1)b\), which contradicts our assumption that \(b\) does not divide \(a\). We are forced to conclude that \(0 \leq r < b\).

We still have to prove that \(q\) and \(r\) are uniquely determined. To do this we suppose 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 \] for integers \(q_1,q_2,r_1,r_2\). 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{equation5.1} r_2-r_1 = b(q_1-q_2).\] This implies that \(b\mid r_2-r_1\). By Theorem 1.4.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{equation5.1}\) 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{divalg}\).

In number theory we usually prefer to work with integers, but if we are willing to consider division of real numbers, it can be shown that when \(a\) is divided by \(b\), the quotient and remainder satisfy \[q = \left \lfloor \frac{a}{b} \right \rfloor \qquad \text{and} \qquad r = a - bq = a - b\left \lfloor \frac{a}{b} \right \rfloor\nonumber \] (see Exercise \(\PageIndex{2}\)).

We now turn to some familiar concepts.

Definition \(\PageIndex{1}\)

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

Definition \(\PageIndex{2}\)

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

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 Exercises \(\PageIndex{5}\) and \(\PageIndex{6}\) at the end of this chapter.

Definition \(\PageIndex{3}\)

For \(b>0\) define \(a\bmod b\) as the value of \(r\) in the pair \(q,r\) satisfying the expressions \(a=bq+r\) and \(0\le r<b\).

In other words, \(a \bmod b\) is the remainder given by the Division Algorithm when \(a\) is divided by \(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}\]

Exercises

Exercise \(\PageIndex{1}\)

Find the values of \(q\) and \(r\) in 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{2}\)

Given integers \(b > 0\) and \(a\), let \(q\) and \(r\) be the quotient and remainder when \(b\) is divided by \(a\), so \(a = bq+r\). Carefully prove that \[q = \left \lfloor \frac ab \right \rfloor.\nonumber \]

Exercise \(\PageIndex{3}\)

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

Exercise \(\PageIndex{4}\)

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{5}\)

Show that for all integers \(n\) the number \(n^3-n\) always has 3 as a factor.

(Hint: by the Division Algorithm, every integer \(n\) falls into one of three cases: \(n=3k\), \(n=3k+1\), \(n=3k+2\). Prove that \(n^3-n\) is divisible by 3 for each of these cases separately.)

Exercise \(\PageIndex{6}\)

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

Exercise \(\PageIndex{7}\)

Prove the following:

1. If \(b>0\) and \(b \mid a\), then \(a \bmod b=0\).
2. If \(b>0\) and \(a \bmod b=0\), then \(b \mid a\).

Exercise \(\PageIndex{8}\)

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{9}\)

1. Use the Division Algorithm to prove the following similar theorem: If \(b > 0\) then for any \(a\) there exists unique integers \(p\) and \(s\) such that \[a=bp+ s\quad\text{and}\quad \left \lfloor -b/2 \right\rfloor < s \leq \left\lfloor b/2 \right \rfloor.\nonumber \]
2. Find integers \(p\) and \(s\) such that \(a=bp+s\) and \(\left \lfloor -b/2 \right\rfloor < s \leq \left\lfloor b/2 \right \rfloor\) for
   1. \(a=36, b = 13\)
   2. \(a=75, b=50\)
   3. \(a=75, b = 49\).