Skip to main content

Section 5.2 The 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.

Exercises 5.2.1 Exercises

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.