Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

1 Answer 1

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.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.