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.