### Section 5.3, problem 16

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.