###### Theorem7.39Division Algorithm

Let \(a\) and \(b\) be integers, with \(b \gt 0\text{.}\) Then there exist unique integers \(q\) and \(r\) such that

\begin{equation*} a = bq + r \end{equation*}where \(0 \leq r \lt b\text{.}\)

\(\newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{\nmid}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\newcommand{\transpose}{\text{t}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\setcounter{chapter}{-1}\)

An application of the Principle of Well-Ordering that we will use often is the division algorithm.

Let \(a\) and \(b\) be integers, with \(b \gt 0\text{.}\) Then there exist unique integers \(q\) and \(r\) such that

\begin{equation*} a = bq + r \end{equation*}where \(0 \leq r \lt b\text{.}\)

This is a perfect example of the existence-and-uniqueness type of proof. We must first prove that the numbers \(q\) and \(r\) actually exist. Then we must show that if \(q'\) and \(r'\) are two other such numbers, then \(q = q'\) and \(r = r'\text{.}\)

*Existence of \(q\) and \(r\text{.}\)* Let

If \(0 \in S\text{,}\) then \(b\) divides \(a\text{,}\) and we can let \(q = a/b\) and \(r = 0\text{.}\) If \(0 \notin S\text{,}\) we can use the Well-Ordering Principle. We must first show that \(S\) is nonempty. If \(a \gt 0\text{,}\) then \(a - b \cdot 0 \in S\text{.}\) If \(a \lt 0\text{,}\) then \(a - b(2a) = a(1 - 2b) \in S\text{.}\) In either case \(S \neq \emptyset\text{.}\) By the Well-Ordering Principle, \(S\) must have a smallest member, say \(r = a - bq\text{.}\) Therefore, \(a = bq + r\text{,}\) \(r \geq 0\text{.}\) We now show that \(r \lt b\text{.}\) Suppose that \(r \gt b\text{.}\) Then

\begin{equation*} a - b(q + 1)= a - bq - b = r - b \gt 0. \end{equation*}In this case we would have \(a - b(q + 1)\) in the set \(S\text{.}\) But then \(a - b(q + 1) \lt a - bq\text{,}\) which would contradict the fact that \(r = a - bq\) is the smallest member of \(S\text{.}\) So \(r \leq b\text{.}\) Since \(0 \notin S\text{,}\) \(r \neq b\) and so \(r \lt b\text{.}\)

*Uniqueness of \(q\) and \(r\text{.}\)* Suppose there exist integers \(r\text{,}\) \(r'\text{,}\) \(q\text{,}\) and \(q'\) such that

Then \(bq + r = bq' + r'\text{.}\) Assume that \(r' \geq r\text{.}\) From the last equation we have \(b(q - q') = r' - r\text{;}\) therefore, \(b\) must divide \(r' - r\) and \(0 \leq r'- r \leq r' \lt b\text{.}\) This is possible only if \(r' - r = 0\text{.}\) Hence, \(r = r'\) and \(q = q'\text{.}\)

Let \(a\) and \(b\) be integers. If \(b = ak\) for some integer \(k\text{,}\) we write \(a \mid b\text{.}\) An integer \(d\) is called a **common divisor** of \(a\) and \(b\) if \(d \mid a\) and \(d \mid b\text{.}\) The **greatest common divisor** of integers \(a\) and \(b\) is a positive integer \(d\) such that \(d\) is a common divisor of \(a\) and \(b\) and if \(d'\) is any other common divisor of \(a\) and \(b\text{,}\) then \(d' \mid d\text{.}\) We write \(d = \gcd(a, b)\text{;}\) for example, \(\gcd( 24, 36) = 12\) and \(\gcd(120, 102) = 6\text{.}\) We say that two integers \(a\) and \(b\) are **relatively prime** if \(\gcd( a, b ) = 1\text{.}\)

Let \(a\) and \(b\) be nonzero integers. Then there exist integers \(r\) and \(s\) such that

\begin{equation*} \gcd( a, b) = ar + bs. \end{equation*}Furthermore, the greatest common divisor of \(a\) and \(b\) is unique.

Let

\begin{equation*} S = \{ am + bn : m, n \in {\mathbb Z} \text{ and } am + bn \gt 0 \}. \end{equation*}Clearly, the set \(S\) is nonempty; hence, by the Well-Ordering Principle \(S\) must have a smallest member, say \(d = ar + bs\text{.}\) We claim that \(d = \gcd( a, b)\text{.}\) Write \(a = dq + r'\) where \(0 \leq r' \lt d\text{.}\) If \(r' \gt 0\text{,}\) then

\begin{align*} r'& = a - dq\\ & = a - (ar + bs)q\\ & = a - arq - bsq\\ & = a( 1 - rq ) + b( -sq ), \end{align*}which is in \(S\text{.}\) But this would contradict the fact that \(d\) is the smallest member of \(S\text{.}\) Hence, \(r' = 0\) and \(d\) divides \(a\text{.}\) A similar argument shows that \(d\) divides \(b\text{.}\) Therefore, \(d\) is a common divisor of \(a\) and \(b\text{.}\)

Suppose that \(d'\) is another common divisor of \(a\) and \(b\text{,}\) and we want to show that \(d' \mid d\text{.}\) If we let \(a = d'h\) and \(b = d'k\text{,}\) then

\begin{equation*} d = ar + bs = d'hr + d'ks = d'(hr + ks). \end{equation*}So \(d'\) must divide \(d\text{.}\) Hence, \(d\) must be the unique greatest common divisor of \(a\) and \(b\text{.}\)

Let \(a\) and \(b\) be two integers that are relatively prime. Then there exist integers \(r\) and \(s\) such that \(ar + bs = 1\text{.}\)