 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/discrete-mathematics-continuous-mathematics-and-probability/3/c/ii/solution

Write

a = q b + r

d ∣ a

and

d ∣ b

, then

d ∣ (a - q b) = r

. Conversely, if

d ∣ b

and

d ∣ r

, then

d ∣ (q b + r) = a

. Therefore

(a, b)

and

(b, r)

have exactly the same positive common divisors, proving

g cd (a, b) = g cd (b, r) .

For

r = 0

, this agrees with

g cd (b, 0) = b

 New to topics? Read the docs here!