2.5 The Remainder Theorem
As we noted at the beginning of this chapter, while we cannot divide integers, we can take the integer part of the quotient along with the remainder.
For example \(13\) divided by \(5\) is gives a quotient of \(2\) with a remainder of \(3\) which we can write as \[13 = 2\cdot 5 + 3.\] We will now prove the following theorem:
If \(a\) and \(b\) are integers with \(a\geq 0\), \(b>0\), then there is a unique pair of integers \(q\) and \(r\) such that \(a=qb+r\text{ and } 0\le r<b.\)
NOTES:
- We refer to the value \(q\) as the quotient and \(r\) as the remainder.
- This result is also referred to as the division algorithm.
- Without the constraint \(0\le r<b\) we could still assert existence of \(q\) and \(r\), but we could not assert uniqueness.
- What happens if we drop the constraints \(a\geq0\), \(b>0\)?
Proof. Theorem 2.14 asserts that something exists and that it is unique. We have to prove both:
Existence: We will prove this by induction. Note we have two independent variables \(a,b\), but we suppose that \(b\) has been chosen and use induction on \(a\). (Since \(b\) can be chosen as any positive value, we will have proved this for all \(b\) as well as all a).
Base step: For \(a=0\) there is s solution of \(a=bq+r\) given by \(q=r=0\). (Using Lemma 2.3.)
Induction step: We assume the result holds for \(a\), that is: there exist integers \(q\) and \(r\) such that \(a=qb+r\text{ and } 0\le r<b.\)
Then \(a+1=(qb+r)+1=qb+(r+1)\).
\(r<b\) so \(r+1\leq b\) by Corollary 2.7.
We now divide into cases: \(r+1=b\) and \(r+1\neq b\) (that is \(r+1<b\)).
Suppose \(r+1<b\). Then \(a+1=qb+r'\) where \(r'=r+1\) and \(r'<b\).
Note that \(0\leq r\) and \(r\leq r+1=r'\) (since \(0<1\)) hence \(0\leq r'\) by (Tr).
Hence if \(r+1<b\) then we have shown that there exists \(q,r'\in\mathbb Z\) such that \(a+1=qb+r'\) and \(0\leq r'<b\), as required.
Now suppose \(r+1=b\). Then \[a+1=qb+b=qb+1b=(q+1)b\] by (Id),(Dist).
Using (Id) again \(a+1=(q+1)b+0\), so we have \(a+1=q'b+r'\) where \(q'=q+1\), \(r'=0\) and \(0\leq r'<b\).
Again we have shown that for \(a+1\) we can find the quotient and remainder as required.
Hence by induction it follows that for all \(a\geq 0\) there exist integers \(q\) and \(r\) such that \(a=qb+r\text{ and } 0\le r<b\).
Uniqueness: Suppose that
\[a=qb+r=q'b+r'\text{ with }0\le r<b\text{ and }0\le r'<b.\]
Then, applying Lemma 2.4, (As), (Comm), \[qb-q'b=qb+r-r-q'b=q'b+r'-r-q'b=r'-r.\] As \(0\leq r\) we have \(-r\leq 0\) (Sh) so \(r'-r\leq r'+0=r'<b\).
If \(q-q'>0\) then \(q-q'\geq 1\) by Theorem 2.6 so \[r'-r=qb-q'b=(q-q')b\geq 1b=b\] by (Dist),(Sc),(Id), which is a contradiction. Hence \(q-q'\leq 0\) so \(q\leq q'\) by (Sh).
But likewise \(q'b-qb=r-r'\) and \(r-r'<b\). So if \(q'-q>0\) then we have a contradiction. We deduce that \(q'\leq q\).
Since \(q\leq q'\) and \(q'\leq q\) we have \(q=q'\) by (ASy). Thus \(q\) is unique.
Moreover \[r-r'=(q'-q)b=0b=0\] by Lemma 2.3 so \(r=r-r'+r'=0+r'=r'\). Hence \(r\) is also unique.