# show that...

• Sep 21st 2008, 05:19 PM
mandy123
show that...
Prove that if a=bq+r, then gcd(a,b)=gcd(b,r)
• Sep 21st 2008, 05:38 PM
Jhevon
Quote:

Originally Posted by mandy123
Prove that if a=bq+r, then gcd(a,b)=gcd(b,r)

Assuming $b \ne 0$, note that $a$ is a multiple of $(b,r)$, since it can be written as a linear combination of $b$ and $r$. So $(b,r) \mid (a,b)$ since $b$ is a multiple of $(b,r)$ as well.

Now use $r = a - bq$ to show that $(a,b) \mid (b,r)$. thus it will follow that $(b,r) \mid (a,b)$ and $(a,b) \mid (b,r)$ so that $(a,b) = (b,r)$