## Section5.2The 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 \}\text{.} \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\text{.} \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\text{.} \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 \}\text{.} \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 )\text{,} \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)\text{.} \end{equation*}

So $d'$ must divide $d\text{.}$ Hence, $d$ must be the unique greatest common divisor of $a$ and $b\text{.}$

Among other things, Theorem 5.2.2 allows us to compute the greatest common divisor of two integers.

Let us compute the greatest common divisor of $945$ and $2415\text{.}$ First observe that

\begin{align*} 2415 & = 945 \cdot 2 + 525\\ 945 & = 525 \cdot 1 + 420\\ 525 & = 420 \cdot 1 + 105\\ 420 & = 105 \cdot 4 + 0\text{.} \end{align*}

Reversing our steps, $105$ divides $420\text{,}$ $105$ divides $525\text{,}$ $105$ divides $945\text{,}$ and $105$ divides $2415\text{.}$ Hence, $105$ divides both $945$ and $2415\text{.}$ If $d$ were another common divisor of $945$ and $2415\text{,}$ then $d$ would also have to divide $105\text{.}$ Therefore, $\gcd( 945, 2415 ) = 105\text{.}$

If we work backward through the above sequence of equations, we can also obtain numbers $r$ and $s$ such that $945 r + 2415 s = 105\text{.}$ Observe that

\begin{align*} 105 & = 525 + (-1) \cdot 420\\ & = 525 + (-1) \cdot [945 + (-1) \cdot 525]\\ & = 2 \cdot 525 + (-1) \cdot 945\\ & = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945\\ & = 2 \cdot 2415 + (-5) \cdot 945\text{.} \end{align*}

So $r = -5$ and $s= 2\text{.}$ Notice that $r$ and $s$ are not unique, since $r = 41$ and $s = -16$ would also work.

To compute $\gcd(a,b) = d\text{,}$ we are using repeated divisions to obtain a decreasing sequence of positive integers $r_1 \gt r_2 \gt \cdots \gt r_n = d\text{;}$ that is,

\begin{align*} b & = a q_1 + r_1\\ a & = r_1 q_2 + r_2\\ r_1 & = r_2 q_3 + r_3\\ & \vdots\\ r_{n - 2} & = r_{n - 1} q_{n} + r_{n}\\ r_{n - 1} & = r_n q_{n + 1}\text{.} \end{align*}

To find $r$ and $s$ such that $ar + bs = d\text{,}$ we begin with this last equation and substitute results obtained from the previous equations:

\begin{align*} d & = r_n\\ & = r_{n - 2} - r_{n - 1} q_n\\ & = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} )\\ & = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2}\\ & \vdots\\ & = ra + sb\text{.} \end{align*}

The algorithm that we have just used to find the greatest common divisor $d$ of two integers $a$ and $b$ and to write $d$ as the linear combination of $a$ and $b$ is known as the Euclidean algorithm.

### Exercises5.2.1Exercises

###### 1.

For each of the following pairs of numbers $a$ and $b\text{,}$ calculate $\gcd(a,b)$ and find integers $r$ and $s$ such that $\gcd(a,b) = ra + sb\text{.}$

1. $14$ and $39$

2. $234$ and $165$

3. $1739$ and $9923$

4. $471$ and $562$

5. $23771$ and $19945$

6. $-4357$ and $3754$

###### 2.

Let $a$ and $b$ be nonzero integers. If there exist integers $r$ and $s$ such that $ar + bs =1\text{,}$ show that $a$ and $b$ are relatively prime.

###### 3.

Let $a$ and $b$ be integers such that $\gcd(a,b) = 1\text{.}$ Let $r$ and $s$ be integers such that $ar + bs = 1\text{.}$ Prove that

\begin{equation*} \gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1\text{.} \end{equation*}
###### 4.

Let $x, y \in {\mathbb N}$ be relatively prime. If $xy$ is a perfect square, prove that $x$ and $y$ must both be perfect squares.

###### 5.

Using the division algorithm, show that every perfect square is of the form $4k$ or $4k + 1$ for some nonnegative integer $k\text{.}$

###### 6.

Suppose that $a, b, r, s$ are pairwise relatively prime and that

\begin{align*} a^2 + b^2 & = r^2\\ a^2 - b^2 & = s^2\text{.} \end{align*}

Prove that $a\text{,}$ $r\text{,}$ and $s$ are odd and $b$ is even.

###### 7.

Let $n \in {\mathbb N}\text{.}$ Use the division algorithm to prove that every integer is congruent mod $n$ to precisely one of the integers $0, 1, \ldots, n-1\text{.}$ Conclude that if $r$ is an integer, then there is exactly one $s$ in ${\mathbb Z}$ such that $0 \leq s \lt n$ and $[r] = [s]\text{.}$ Hence, the integers are indeed partitioned by congruence mod $n\text{.}$

###### 8.

Define the least common multiple of two nonzero integers $a$ and $b\text{,}$ denoted by $\lcm(a,b)\text{,}$ to be the nonnegative integer $m$ such that both $a$ and $b$ divide $m\text{,}$ and if $a$ and $b$ divide any other integer $n\text{,}$ then $m$ also divides $n\text{.}$ Prove there exists a unique least common multiple for any two integers $a$ and $b\text{.}$

###### 9.

If $d= \gcd(a, b)$ and $m = \lcm(a, b)\text{,}$ prove that $dm = |ab|\text{.}$

###### 10.

Show that $\lcm(a,b) = ab$ if and only if $\gcd(a,b) = 1\text{.}$

###### 11.

Prove that $\gcd(a,c) = \gcd(b,c) =1$ if and only if $\gcd(ab,c) = 1$ for integers $a\text{,}$ $b\text{,}$ and $c\text{.}$

###### 12.

Let $a, b, c \in {\mathbb Z}\text{.}$ Prove that if $\gcd(a,b) = 1$ and $a \mid bc\text{,}$ then $a \mid c\text{.}$

###### 13.Fibonacci Numbers.

The Fibonacci numbers are

\begin{equation*} 1, 1, 2, 3, 5, 8, 13, 21, \ldots\text{.} \end{equation*}

We can define them inductively by $f_1 = 1\text{,}$ $f_2 = 1\text{,}$ and $f_{n + 2} = f_{n + 1} + f_n$ for $n \in {\mathbb N}\text{.}$

1. Prove that $f_n \lt 2^n\text{.}$

2. Prove that $f_{n + 1} f_{n - 1} = f^2_n + (-1)^n\text{,}$ $n \geq 2\text{.}$

3. Prove that $f_n = [(1 + \sqrt{5}\, )^n - (1 - \sqrt{5}\, )^n]/ 2^n \sqrt{5}\text{.}$

4. Show that $\lim_{n \rightarrow \infty} f_n / f_{n + 1} = (\sqrt{5} - 1)/2\text{.}$

5. Prove that $f_n$ and $f_{n + 1}$ are relatively prime.