Show that if a > b ≥ 0 then gcd(a, b) = gcd(a-b, b).
Proof: The proof closely follows the proof of Theorem 5.3.2 on page 206 of the text.
Our goal is to show that the set of common divisors of a and b is the same as the set of common divisors of a-b and b. Once we have proven this, we can conclude that the greatest common divisor of a and b must be the same as the greatest common divisor of a-b and b.
Part 1: We show that {Common divisors of a and b} ⊆ {Common divisors of a-b and b}.
Suppose c is a common divisor of a and b.
Then we can write a = qc and b = sc for some integers q and s. (Because c evenly divides a, a/c =q must be an integer.)
To show that c is a common divisor of a-b and b, we only need to show that c divides a-b; we already know that c divides b.
a-b = qc-sc = (q-s)c
so c divides a-b. (Because (a-b)/c = (q-s) is an integer.)
We conclude that all common divisors of a and b must also be common divisors of a-b and b.
Part 2: We show that {Common divisors of a-b and b} ⊆ {Common divisors of a and b}.
Suppose d is a common divisor of a-b and b.
Then we can write a-b = td and b = vd for some numbers t and v.
We already know that d is a divisor of b, so to show that d is a common divisor of a and b we only need to show that d divides a.
a = (a-b) + b = td + vd = (t + v) d.
We see that a/d = t + v is an integer, so d divides a.
We conclude that all common divisors of a-b and b are also common divisors of a and b.
Combining parts 1 and 2 we see that {Common divisors of a and b} = {Common divisors of a-b and b}, because if A is a subset of B and B is a subset of A then A must equal B.
So the greatest common divisor of a and b must equal the greatest common divisor of a-b and b.
The proof is complete.