Complete the proof of Lemma by proving the following: If a and b are any integers with b ≠...

Complete the proof of Lemma by proving the following: If a and b are any integers with b ≠ 0 and q and r are any integers such that

a = bq + r.

then

gcd(b, r) ≤ gcd(a, b).

Lemma

If a and b are any integers not both zero, and if q and r are any integers such that

a = bq + r,

then

gcd(a, b)= gcd(b, r).

Proof:

[The proof is divided into two sections: (1) proof that gcd(a, b) ≤ gcd(b, r ), and (2) proof that gcd(b, r ) ≤ gcd(a, b). Since each gcd is less than or equal to the other, the two must be equal.]

1. gcd (a, b) ≤ gcd (b, r):

a. [We will first show that any common divisor of a and b is also a common divisor of b and r.]

Let a and b be integers, not both zero, and let c be a common divisor of a and b. Then c | a and c | b, and so, by definition of divisibility, a = nc and b = mc, for some integers n and m. Now substitute into the equation

a = bq + r

to obtain

nc = (mc)q + r.

Then solve for r:

r = nc − (mc)q = (n − mq)c.

But n − mq is an integer, and so, by definition of divisibility, c | r . Because we already know that c | b, we can conclude that c is a common divisor of b and r [as was to be shown].

b. [Next we show that gcd(a, b) ≤ gcd(b, r ).]

By part (a), every common divisor of a and b is a common divisor of b and r . It follows that the greatest common divisor of a and b is definedbecause a and b are not both zero, and it is a common divisor of b and r. Butthen gcd(a, b) (being one of the common divisors of b and r ) is less than orequal to the greatest common divisor of b and r :

gcd(a, b)≤ gcd(b, r).

---

2. gcd (b, r) ≤ gcd (a, b):

The second part of the proof is v ery similar to the first part. It is left as exercise 10 at the end of the section.