7.2: The Division Algorithm

The Division Algorithm, Theorem 7.11, is the result that guarantees that long division of natural numbers will terminate in a unique quotient and remainder with the remainder strictly smaller than the divisor. Long division is difficult and tedious for young students. Typically it is the most challenging computation that elementary school students are expected to master. You may have revisited the algorithm again when you learned to divide polynomials. Here the Division Algorithm says that the quotient and remainder are unique and the remainder is either identically 0 or has degree strictly smaller than the divisor. We frequently compare the arithmetic of integers and the arithmetic of polynomials, and it is the Division Algorithm that makes this comparison useful.

Let’s extend the link between integer combinations and greatest common divisors. According to Lemma 7.2, a pair of integers are relatively prime if there is an integer combination of the pair which equals 1. This result generalizes to greatest common divisors other than \(1 .\)

THEOREM 7.7. Let \(a, b \in \mathbb{Z}\). The set of integer combinations of a and \(b\) equals the set of integer multiples of \(\operatorname{gcd}(a, b)\).

PROOF. Let \(c=\operatorname{gcd}(a, b)\) and \[M=\{k c \mid k \in \mathbb{Z}\} .\] Since \(c\) is a divisor of \(a\) and \(b\), there are \(i, j \in \mathbb{Z}\) such that \[a=i c\] and \[b=j c .\] Let \[I=\{m a+n b \mid m, n \in \mathbb{Z}\} .\] We show first that \(I \subseteq M\).

If \(m, n \in \mathbb{Z}\), then \[m a+n b=m i c+n j c=(m i+n j) c .\] Hence every integer combination of \(a\) and \(b\) is a multiple of \(c\) and \[I \subseteq M .\] Now we show that \(M \subseteq I\). Let \(k c \in M\) and \[r=\operatorname{gcd}(i, j) .\] Then there are \(m, n \in \mathbb{Z}\) such that \[r m c=i c=a\] and \[r n c=j c=b .\] So \(r c \mid a\) and \(r c \mid b\). Hence \[\operatorname{gcd}(a, b) \geq r c \geq c .\] However \(\operatorname{gcd}(a, b)=c\), and thus \(r=1\). Therefore \(i\) and \(j\) are relatively prime.

By Proposition 7.2, there is an integer combination of \(i\) and \(j\) that equals 1 . Let \(u, v \in \mathbb{Z}\) be such that \[u i+v j=1 .\] Then \[c(u i+v j)=c\] and \[k c=k c(u i+v j)=k(u a+v b)\] by equations \(7.14\) and \(7.15\). Hence \[k c \in I,\] and as \(k\) was arbitrary, \[M \subseteq I .\] COROLLARY 7.8. Let \(a, b \in \mathbb{Z}\). Then \(\operatorname{gcd}(a, b)\) is the smallest positive integer combination of \(a\) and \(b\).

Theorem \(7.7\) tells us that the integer combinations of \(a\) and \(b\) are precisely the integer multiples of \(\operatorname{gcd}(a, b)\) (which happens to be the smallest positive integer combination of \(a\) and \(b)\). We think of \(\operatorname{gcd}(a, b)\) as "generating" through multiplication the set of integer combinations of \(a\) and \(b\). PROPOSITION 7.9. Let \(a, b, k \in \mathbb{Z}\). Then \[\operatorname{gcd}(a, b)=\operatorname{gcd}(a-k b, b) .\] Proof. If \(c \in \mathbb{Z}, c \mid a\) and \(c \mid b\), then \(c \mid a-k b\). Therefore \[\operatorname{gcd}(a, b) \leq \operatorname{gcd}(a-k b, b) .\] Likewise, if \(c \mid a-k b\) and \(c \mid b\), then \(c \mid a\), so we get the reverse inequality of (7.10), so the two sides are equal.

THEOREM 7.11. Division Algorithm Let \(a, b \in \mathbb{Z}, b \neq 0\). Then there are unique \(q, r \in \mathbb{Z}\) such that \[a=q b+r\] where \(0 \leq r<|b|\).

Discussion. In the Division Algorithm \(a\) is called the dividend, \(b\) the divisor, \(q\) the quotient, and \(r\) the remainder.

Proof. Let \(a, b \in \mathbb{Z}\) and \(b \neq 0\). Define \(I \subseteq \mathbb{N}\) by \[I=\{a-k b \mid k \in \mathbb{Z}\} \cap \mathbb{N} .\] \(I\) has a smallest element, \(a-q b\), for some \(q \in \mathbb{Z}\).

Claim: \(0 \leq a-q b<|b|\).

Proof of Claim.

We argue by cases.

Case 1: \(b>0\)

If \(a-q b \geq b\) then \[a-(q+1) b \geq 0 .\] Hence \[a-(q+1) b \in I .\] However \(a-q b\) is minimal in \(I\), so this is impossible. Therefore \[a-q b<|b| \text {. }\] Case 2: \(b<0\)

If \(a-q b \geq|b|\), then \[a-q b>a-(q-1) b \geq 0 .\] As in the first case \[a-(q-1) b \in I\] This is impossible since by assumption \(a-q b\) is minimal in \(I\). Therefore \[a-q b<|b|\] Thus if \[r:=a-q b\] we have \(a=q b+r\) and \(0 \leq r<|b|\). It remains to show that the quotient and remainder are unique. Suppose \[a=m b+r=n b+s\] where \(0 \leq r, s<|b|\). If \(r=s\) then \(m b=n b\) and \(m=n\). So we assume that \(r \neq s\). Without loss of generality we assume that \(r<s\). Then, \[0 \leq s-r=(m-n) b<|b|\] So \(m-n=0\) and \(r=s\), a contradiction.

Of course, \(q\) and \(r\) could be found by long division - that is, one may subtract multiples of \(b\) until the remainder is less than \(|b|\).