Euclidean algorithm

[Zareon]

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.

[the tree]

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.

[matt grime]

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.

[Zareon]

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!

[Dave]

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