# Divisibility: Remainders and Greatest Common Divisors [duplicate]

Possible Duplicate:
Why is $\gcd(a,b)=\gcd(b,r)$ when $a = qb + r$?

Any idea how to prove that if $a,b \in \Bbb Z$ with $b = aq + r$, then $\gcd(a,b) = \gcd(a,r)$?

-

## marked as duplicate by Alex Becker, Arturo Magidin, mixedmath♦, Chris Eagle, Zev ChonolesJun 8 '12 at 15:36

HINT Note that any common divisor of $a$ and $b$ divides $r$. (Why?) Similarly, any common divisor of $a$ and $r$ divides $b$. (Why?) – user17762 May 23 '12 at 5:23
Prove $\gcd(a,b)=\gcd(a,b-a)$, then invoke induction. – anon May 23 '12 at 5:23

Note that $k$ divides both $a$ and $b$ if and only if it divides both $a$ and $b+ta$ for any $t$. (Prove that if it divides $a$ and $b$ then it divides $a$ and $b+ta$. The converse follows by applying the argument again to $a$ and $b+ta$ to get $a$ and $(b+ta)+(-t)a$.

Now, if $b=aq+r$ then we have: \begin{align*} k|a,b &\iff k|a,b+a(-q)\\ &\iff k|a,r \end{align*} So the set of common divisors of $a$ and $b$ and the set of common divisors of $a$ and $r$ coincides.

-