# Thread: 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 $\displaystyle (1)\; c\mid a$ and $\displaystyle (2)\; c\mid b$. From (1) it follows that $\displaystyle (3)\; c\mid qa$, and from (3),(2) it follows that $\displaystyle c \mid b-qa$. But $\displaystyle b-qa=r$, so that $\displaystyle c$ divides both $\displaystyle r$ and (from (1)) $\displaystyle a$. The other direction ($\displaystyle c\mid r,\; c\mid a \Rightarrow c\mid b$) follows in the same manner.

3. Thanks for the help there