View Single Post
boombaby
#4
Nov9-08, 11:20 AM
P: 130
A proof involving Greatest common divisors

Now you have c|a and c|b. you get c|r from jeffreydk's hint.
Then you have c|b and c|r, which implies c|gcd(b,r), which means c is a common divisor of b and r.
if c=gcd(a,b), you are supposed to show c is actually the GREATEST common divisor of b and r

here's another way, gcd(a,b)|gcd(b,r) and gcd(b,r)|gcd(a,b) will imply they are equal. I think you have already got gcd(a,b)|gcd(b,r), you can prove gcd(b,r)|gcd(a,b) in a similar way.