Printable View

Prove that if a=bq+r, then gcd(a,b)=gcd(b,r)

Quote: 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