Thread: Number theory question i'm stuck on during exam revision

Let a, b, q, r be integers such that b=aq+r and a doesn't = 0. SHow that an integer c is a common divisor of b and a if and only if c is a common divisor of a and r. Explain why this means that gcd(b,a)= gcd(a,r).

Here's the question i'm struggling with. I know that it is related to the Euclidean algorithm in some way and that i somehow need to show that c divides (a,b) and (a,r). I can also see that using ax +by = c will be helpful. I just can't seem to pull all my thoughts together so any help would be grateful.

Assume and . From (1) it follows that , and from (3),(2) it follows that . But , so that divides both and (from (1)) . The other direction ( ) follows in the same manner.

Thanks for the help there