Complete the proof of Lemma by proving the following: If a

Solution : to Prove that gcd(a, b)= gcd(b, r).

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

a = bq + r ……………………………………(1)

then

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

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

Proof:

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 …………………………………………..(1)

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