# Math Help - Number theory question i'm stuck on during exam revision

1. ## 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.

2. Assume $(1)\; c\mid a$ and $(2)\; c\mid b$. From (1) it follows that $(3)\; c\mid qa$, and from (3),(2) it follows that $c \mid b-qa$. But $b-qa=r$, so that $c$ divides both $r$ and (from (1)) $a$. The other direction ( $c\mid r,\; c\mid a \Rightarrow c\mid b$) follows in the same manner.

3. Thanks for the help there