$\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}$

# Section7The Division Algorithm

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

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

\begin{equation*} S = \{ a - bk : k \in {\mathbb Z} \text{ and } a - bk \geq 0 \}. \end{equation*}

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

\begin{equation*} a = bq + r, 0 \leq r \lt b \quad \text{and}\quad a = bq' + r', 0 \leq r' \lt b. \end{equation*}

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

\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{.}$