Zareon Posted September 6, 2006 Share Posted September 6, 2006 Can anyone please explain why gcd(n,m)=gcd(n-m,m)? (n>=m) It's like everyone assumes it because, apparantly, it's so obvious, but I don't see it. Link to comment Share on other sites More sharing options...

the tree Posted September 6, 2006 Share Posted September 6, 2006 Can anyone please explain why gcd(n' date='m)=gcd(n-m,m)? (n>=m)[/quote']Not really sure what you're looking for. I think your question isn't really to do with the algorithm, are you looking for a proof of the identity you gave? Is it clear to you that if r is a divisor of n and m then r will also be a divisor of n-m? And can you see that'd it'd be impossible for the GD to get bigger with a smaller number, so r is still the GCD? It's like everyone assumes it because, apparantly, it's so obvious, but I don't see it.Lots of things aren't obvious that get assumed, "the" quadratic equation for instance. I can never remember how that is derived. Link to comment Share on other sites More sharing options...

matt grime Posted September 7, 2006 Share Posted September 7, 2006 It's not necessary to try to 'see that the GD can't get bigger'. If d divides x and y it divides ax+by for integers a and b. So in particular the divisors of n and m are the same as the divisors of n-m and m (you don't actually need the restriction on n=>m: divisors are well defined for negative numbers). So the set of divisors of n and m is the same as the set of divisors of n-m and m, hence the largest element in each of those two sets must be the same. Link to comment Share on other sites More sharing options...

Zareon Posted September 7, 2006 Author Share Posted September 7, 2006 It's not necessary to try to 'see that the GD can't get bigger'. If d divides x and y it divides ax+by for integers a and b. So in particular the divisors of n and m are the same as the divisors of n-m and m (you don't actually need the restriction on n=>m: divisors are well defined for negative numbers). So the set of divisors of n and m is the same as the set of divisors of n-m and m' date=' hence the largest element in each of those two sets must be the same.[/quote'] Ah, I see. It's so freaking obvious now. Thanks! Link to comment Share on other sites More sharing options...

Dave Posted September 7, 2006 Share Posted September 7, 2006 gcd questions can always be a little tricky to prove because of the definition. Once you've done a few proofs they do become easier Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now