The division algorithm and the Euclidean algorithm are two of the oldest results in modern use. The former gives us existence and uniqueness of quotients and remainders for positive integer division, and the latter establishes a method to obtain the greatest common divisor of two integers through repeated application of the division algorithm. Though there exist much more sophisticated and faster algorithms in terms of computational steps for reaching the same ends, these two are straightfoward and the basis upon which improvements are compared.
Since we built up a sufficient base to prove the division algorithm in the previous lesson, we open with its statement and proof.
Theorem 2.1. Given positive integers $a$ and $b$, $b \neq 0$, there exist unique integers $q$ and $r$, with $0 \leq r \lt b$ such that $a = bq + r$.
Note 1: It is standard practice when stating this theorem to use $q$ and $r$ since they denote, respectively, a quotient and a remainder.
Note 2: This is what's called an "existence and uniqueness" proof. The strategy thus requires two steps - to show that the values desired exist, and that the result is a unique one. Uniqueness is shown generally by positing there are two solutions and deriving that they must be equal through some means or another. It's a standard strategy, and one you should study carefully for understanding mathematical proof structures.
Proof: Since $a$ and $b$ are both positive integers, consider the set of non-negative integers given by $ \{ a, a-b, a-2b, \dots \}$. It's bounded below by $0$, and so contains a least element by the least integer principle. Call that value $a-qb$. Note that $a-(q+1)b \lt 0$ by this construction, so $q$ is in fact the greatest multiple of $b$ that can be subracted from $a$. Now let $r = a-bq$. This gives us both of $q$ and $r$, so this suffices to show the existence of $q$ and $r$ such that $a= bq + r$.
Next, we need to show uniqueness. As previously described, the strategy here is to posit a second candidate pair, and show that they are the same as the originally desired values.
Suppose then that there exist values $q'$ and $r'$ also satisfying the conditions; that is, suppose $a = bq+r = bq'+r'$, with $0 \leq r \lt b$ and $0 \leq r' \lt b$. By subtraction, we have $0 = b(q-q')+(r-r')$. Since $b$ divides both $0$ and $b(q-q')$, it must divide the other term, by Lemma 1: $b \vert (r-r')$. But by the previous inequalities on $r$ and $r'$, it must be the case that $-b \lt r-r' \lt b$, and the only multiple of $b$ between $-b$ and $b$ is $0$. Therefore, $r-r'=0$, establishing that $r=r'$. Since the remainders are the same, the fact that $0 = b(q-q')+(r-r')$ means that $q-q'=0$ as well. This suffices to establish uniqueness of $q$ and $r$, and completes the proof of the Euclidean division algorithm.
Lemma 3. If $a = bq + r$, then $(a,b)=(b,r)$.
Proof: First, we seek to show that, given $(a,b)$, it follows that the value of $(b,r)$ is the same. Let $d = (a,b)$. By Lemma 1, if $d \vert a$ and $d \vert b$ and $a = bq+r$, then $d \vert r$. Now we seek to show that $d$ is the greatest common divisor of $b$ and $r$ - suppose that $c$ is any common divisor of $b$ and $r$. By Lemma 1 again, it follows that $c$ divides $a$ as well, and so $c$ is a divisor of both $a$ and $b$. Since $c$ and $d$ are both divisors of $a$ and $b$, it follows that $c \leq d$. This suffices to show that $d = (b,r)$.
Note: We could have easily started from $d = (b,r)$ and gone the other way just as readily, and it might be helpful to convince yourself of this.
Theorem 3. Given positive integers $a$ and $b$, $b \neq 0$, we may compute the value of $(a,b)$ by repeated application of the Division Algorithm in the following way:
| $a = bq_0 + r_0$ | $0 \leq r \lt b$ |
|---|---|
| $b = rq_1 + r_1$ | $0 \leq r_1 \lt r$ |
| $r = r_1q_2 + r_2$ | $0 \leq r_2 \lt r_1$ |
| $\vdots$ | $\vdots$ |
| $r_k = r_{k+1} q_{k+2} + r_{k+2}$ | $0 \leq r_{k+2} \lt r_{k+1}$ |
Specifically, for sufficiently large $k$, say $k = t$, we have $ r_{t-1} = $r_t q_{t+1} $, and subsequently, $(a,b)=r_t$.
Proof: First, observe that the sequence of non-negative integers given by $ \{ b, r, r_1, \dots, \} $ is strictly decreasing by the division algorithm, and is bounded below by zero. Therefore, it has a final element before the remainders reach $0$. Let the first $0$ element be $ r_{t+1} $. Then $r_{t-1} = r_t q_{t+1} $, noting that $r_t$ divides both sides. Now, apply Lemma 3 repeatedly to the sequence of equalities given by the division algorithm, working back up the chart.
This repeated application of Lemma 3 tells us that $r_t = (r_{t-1}, r{t}) = \cdots = (b,r) = (a,b)$, and completes the proof.
Note: If either of $a$ and $b$ are negative, you may want to convince yourself that $(a,b) = (\pm a, \pm b)$ and see that the proof follows just the same.
Note: This is not given in the text by Dudley, but is a very nice proof to see and shortcuts the subsequent theorem. Therefore we will call it Theorem 3.5. As the proof has several moving parts, I don't fault Dudley for skipping it in a text of this level. However, it gives two immediate corollaries that are themselves very powerful.
Theorem 3.5: Let $d = (a,b)$ for positive integers $a$ and $b$. Then for all integers of the form $as+bt$, with integers $s$ and $t$, there exists some $n$ such that $nd = as+bt$. Hence, every linear combination of $a$ and $b$ is a multiple of $(a,b)$, and vice versa - every multiple of $(a,b)$ is a linear combination of $a$ and $b$.
Proof: Suppose $x$ is a linear combination of $a$ and $b$ - that is, $x = as+bt$. We want to show that $x$ is also some multiple of $(a,b)$. Since $d = (a,b)$, we know that there are some values $f$ and $g$ such that $a = fd$ and $b = gd$. Substitute these values into the original expression for $x$ and we see that $x = d(fs+gd)$, with the expression in parenthesis as an integer. Therefore, $d$ divides $x$, and so there is some $n$ such that $nd = x$.
Now we go the opposite direction: Suppose we have a multiple of $(a,b)$ expressible in the form $nd$. We seek to show it can be expressed as a linear combination of $a$ and $b$ of the form $as+bt$. To demonstrate this, we must consider the entire class of integers generated by linear combinations of $a$ and $b$.
Let's restrict our consideration of integers of the form $as+bt$ such that $as+bt \gt 0$ - that is, only the positive elements. It's clearly nonempty (consider $s=0$, $t=1$ or vice-versa), and bounded below (by $0$), so it must have a least element by the least integer property. Let's call that least integer $e$. Then $e = as' + bt'$ for some particular integers $s'$ and $t'$. We already know that $a$ and $b$ themselves of this form, so $e \leq a$ and $e \leq b$.
Start with considering the fact that $e \leq a$. Now, by the division algorithm, we can write $a = eq + r$ for some integers $q$ and $r$, with $0 \leq r \lt e$. If $r \gt 0$,then we have the following:
$r = a - eq = a - (as'+bt')q = a(1-s'q)+b(-t'q) $
This means $r$ is also a linear combination of $a$ and $b$. But the division algorithm also specifies $0 \leq r \lt e$. If that first inequality is strict and $r \gt 0$, this contradicts the minimality of $e$, so it must be the case that $r = 0$. This means that $a = eq$, so $e \vert a$.
Next, consider that $e \leq b$. By an identical argument, we can also see that $e \vert b$, and conclude that $e$ is a common divisor of $a$ and $b$.
Having established that $e$ is a common divisor of $a$ and $b$, we now must show it's the greatest common divisor. So suppose we have some common divisor, $f$ of $a$ and $b$. Since $f \vert a$ and $f \vert b$, $f \vert (ax+by)$ for any integers $x$ and $y$ - and specifically, $f \vert (as'+bt')$. And since $as'+bt' = e$, $f \vert e$ - and so $f \leq e$. Since $e$ is itself a common divisor of $a$ and $b$, and any arbitrary common divisor $f$ is not greater than $e$, this means $e$ must be the greatest common divisor. It then follows that $d = e$.
Since we've established that $d$ is able to be expressed as a linear combination of $a$ and $b$, we can obtain any multiple of $d$, $nd$, by simply multiplying through by $n$ - that is, if $d = as'+ bt'$, then $nd = ans'+ bnt'$. This suffices to show that any multiple of $d = (a,b)$ is able to be expressed as a linear combination of $a$ and $b$.
Corollary 3.5.1: The greatest common divisor of two nonzero integers $a$ and $b$ is the smallest positive integer among all their linear combinations. That is, for all integers $s$ and $t$, $(a,b)$ is the smallest positive element of the integers described by $as+bt$.
This fact was shown directly in the preceding proof as part of the demonstration that any multiple of $(a,b)$ is expressible in the form $as+bt$.
Corollary: Two values are coprime if and only if some linear combination of them equals $1$.
Corollary 3.5.2: Given nonzero values $a$ and $b$, $(a,b) = 1$ if and only if there exist integers $s$ and $t$ such that $as + bt = 1$.
Proof of corollary: First, suppose $(a,b)=1$. The existence of such $s$ and $t$ follows immediately from theorem 3.5. Next, suppose there exist $s$ and $t$ such that $as + bt = 1$. By corollary 3.5.1, $(a,b)$ is the least positive integer able to be expressed of the form $as+bt$, and there are no positive integers less than 1. Therefore, it must be the case that $(a,b) = 1$.
What follows is now the trajectory given by Dudley in his text. Given we have a bit of a sledgehammer from the previous theorem and corollaries, these should be pretty easy to convince yourself of as stated by Dudley.
Theorem 4: If $(a,b)=d$, then there are integers $x$ and $y$ such that $ax+by = d$.
Proof: By theorem 3.5, all multiples of $d=(a,b)$ can be expressed as a linear combination of $a$ and $b$. Notably, $d$ is a multiple of itself, with $n=1$.
Note: Dudley says this can be proved simply by working the Euclidean algorithm backward. This is substantially what is done in the proof of Theorem 3.5.
Corollary 4.1: If $d \vert ab$ and $(d,a)=1$, then $d \vert b$.
Proof: As $d$ and $a$ are relatively prime, there are integers $s$ and $t$ such that $ds + at = 1$. Multiply both sides of this by $b$ to obtain
$d(bs)+(ab)t = b $
By hypothesis, $d \vert (ab)$, and clearly $d$ divides $d(bs)$ as well, so it follows that $d$ divides the left hand side of this equation. Therefore, $d$ must also divide the right hand side: $b$.
Note: It is worth convincing yourself that this doesn't work if we remove the condition on $d$ and $a$ being relatively prime. Consider trying it with a few.
Corollary 4.2: Let $(a,b)=d$, and suppose that $c\vert a$ and $c \vert b$. Then $c \vert d$.
Proof: We actually showed this in the proof of Theorem 3.5.
Corollary 4.3: If $a \vert m$, $b \vert m$, and $(a,b) = 1$, then $ab \vert m$.
Proof: Since $b$ divides $m$, there is some integer $q$ such that $m = bq$. And since $a$ divides $m$ as well, $a \vert bq$. Since $a$ and $b$ are relatively prime, then Corollary 4.1 tells us that $a \vert q$. Therefore, there's some integer $r$ such that $q = ar$. Substituting through again, we see that $m = bq = bar$. Therefore, $ab \vert m$.
The problems provided at the end of the chapter are first a few calculation problems, followed by some more interesting abstract ones. Since I'm less interested in calculation, I'll reproduce a few of the later ones here:
Problem 10.
Solution:
Exercise 11.
Solution:
First, suppose $(k,n+k) = 1$. We seek to show $(k,n) = 1$. By theorem 3.5, there are integers $s$ and $t$ such that $ks+(n+k)t = 1$. But regrouping also shows us that $k(s+t)+nt=1$ - that is, $1$ is a linear combination of $n$ and $k$. By the other direction of theorem 3.5, this means that $(n,k) = 1$.
Now, suppose $(n,k) = 1$. We seek to show $(k,n+k) = 1$. Again, apply theorem 3.5: $(n,k)=1$ implies there are integers $s$ and $t$ such that $ns+kt=1$. Rearrange to obtain
Exercise 1.12. Prove: If $c \vert ab$ and $(c,a) = d$, then $c \vert db$.
Exercise 15.
Solution:
Under construction
Background: Mathematics 3D Blender Illustration
Credit: MasterTux
Source: creazilla
License: CC0-1.0
Modifications: Rotated and darkened