Prove that if a=bq+r, then gcd(a,b)=gcd(b,r)
Follow Math Help Forum on Facebook and Google+
Originally Posted by mandy123 Prove that if a=bq+r, then gcd(a,b)=gcd(b,r) Assuming , note that is a multiple of , since it can be written as a linear combination of and . So since is a multiple of as well.
Now use to show that . thus it will follow that and so that