0
$\begingroup$

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)$?

  • 1
    **HINT** Note that any common divisor of $a$ and $b$ divides $r$. (Why?) Similarly, any common divisor of $a$ and $r$ divides $b$. (Why?)2012-05-23
  • 0
    Prove $\gcd(a,b)=\gcd(a,b-a)$, then invoke induction.2012-05-23

1 Answers 1