Lemma: If $a = bq+r$, then $\gcd(a,b) = \gcd(b,r)$
Things you should know already
Before you can be comfortable with the proof at the end of this article, you should be comfortable with these concepts:
- Proving two sets are equal
- The definition of divides, such as $a|b$.
Examples
Jumping in and immediately trying to prove something we may not fully understand is a recipe for frustration! Let's take a look at some examples to fuel our intuition.
The lemma states if we have a number $a$ in the form of $bq+r$, then the gcd of $(a,b)$ should be the same as the gcd of $(b,r)$.
1) $26 = (6)4 + 2$
- $a=26$, $b=6$, $r=2$
- common divisors of $26$ and $6$: $(1, 2)$
- common divisors of $6$ and $2$: $(1, 2)$
- $\gcd(a,b) = 2$, $\gcd(b,r) = 2$
2) $60 = (24)2 + 12$
- $a=60$, $b=24$, $r=12$
- common divisors of $60$ and $24$: $(1, 2, 3, 4, 6, 12)$
- common divisors of $24$ and $12$: $(1, 2, 3, 4, 6, 12)$
- $\gcd(a,b) = 12$, $\gcd(b,r) = 12$
3) $110 = (30)3 + 20$
- $a=110$, $b=30$, $r=20$
- common divisors of $110$ and $30$: $(1, 2, 5, 10)$
- common divisors of $30$ and $20$: $(1, 2, 5, 10)$
- $\gcd(a,b) = 10$, $\gcd(b,r) = 10$
So it seems that not only do $(a,b)$ and $(b,r)$ share the same greatest common divisor, they share all common divisors. If we can prove that the set of common divisors of $(a,b)$ and the set of common divisors of $(b,r)$ are the same, simply choosing the greatest value in the set will get us the $\gcd$.
Supporting theorems
Before we can prove the lemma, we need the help of a supporting theorem.
Theorem: If $c$ divides $a_{1}, \dots,\ a_{k}$, then $c$ divides $a_{1}u_{1} + \dots + a_{k}u_{k}$ for all integers $u_{1}, \dots ,u_{k}$.
The following corollary summarizes the theorem for the case of two numbers:
Corollary: If $c$ divides $a$, and $c$ divides $b$, then $c$ divides $au+bv$ for all $u,v \in \mathbb{Z}$.
Example
Observe $3$ divides $6$ and $9$. Then we can add $6u+9v$ for all $u,v \in \mathbb{Z}$, and $3$ will divide the result.
Why is this useful?
We need some way to relate the divisors of $(a,b)$ to the divisors of $(b,r)$. The corollary gives us that relationship.
Take a look at $$a = bq + r$$ We can rewrite that as $$a = b(q) + r(1)$$.
According to the corollary, if we are know that $d$ divides $b$ and $r$, then we can conclude that $d$ divides $b(q) + r(1)$, which is equal to $a$, thus $d | a$.
The proof strategy
The strategy for the proof is to first create two sets. One set will be the common divisors of $(a,b)$, the other set will be the common divisors of $(b,r)$. We will choose an arbitrary element in one set, and use the corollary to show it is contained in the other. We'll do this operation for both sets to demonstrate double containment, implying the sets are equal. Once we've concluded the two sets are equal, we can just say that the largest value in the set is the greatest common divisor.
Proof
Suppose $a = bq +r$. Let $D = \{d \in \mathbb{Z} \mid d|a, d|b\}$, and
let $D' = \{d \in \mathbb{Z} \mid d|b, d|r\}$.
Let $x \in D$. So $x|a$ and $x|b$. Observe
\begin{align*}
a &= bq + r \\
a - bq &= r \\
a(1) + b(-q) &= r
\end{align*}
By the corollary, $x$ divides $a(1)+b(-q)$, which is equal to $r$, thus $x|r$.
Since $x|b$ and $x|r$, $x \in D'$. So $D \subseteq D'$.
Let $x \in D'$. So $x|b$ and $x|r$. Observe
\begin{align*}
a &= bq + r \\
a &= b(q) + r(1) \\
\end{align*}
By the corollary, $x$ divides $b(q)+r(1)$, which is equal to $a$, thus $x|a$.
Since $x|b$ and $x|a$, $x \in D$. So $D' \subseteq D$.
By double containment, we have shown $D = D'$, meaning the common divisors of
$(a,b)$ and the common divisors of $(b,r)$ are equal. $\gcd(a,b)$ and
$\gcd(b,r)$ are thus identical, and equal to the largest value of the set. QED.