# Another GCD Proof

• Mar 2nd 2013, 05:31 PM
PrettySmart10
Another GCD Proof
Im new to the forum so im not sure if im posting in the right section but ive been stuck on this problem for days however im not sure on how to even go about it. I would at the very least need some advice on how to tackle this problem. (Headbang)

Claim: For every pair of positive natural numbers (m, n), if m >= n, then gcd(m, n) = gcd(n, m-n)

• Mar 2nd 2013, 05:34 PM
emakarov
Re: Another GCD Proof
If you show that the sets of common divisors of these two pairs of numbers coincide, you automatically show that the maximums of these sets also coincide.
• Mar 2nd 2013, 05:49 PM
Jame
Re: Another GCD Proof
If d = gcd(m,n), then d divides ANY linear combination of m and n.

i.e $\displaystyle d \;| \;mx + ny \;\forall\; x,y \in \mathbb{Z}$
• Mar 2nd 2013, 06:33 PM
PrettySmart10
Re: Another GCD Proof
So could I say

let d be the common divisor that is a integer

then let n = d*i and m = d*j; j, and i being any positive integers

since n,m and m-n should be multiples of the same divisor.

then m-n = d*j - d*i

then m-n = d*(j-i) ; Then let k = j-i which also represents any integer

hence d|n and d|m and d|m-n

would this be right?
• Mar 2nd 2013, 06:52 PM
emakarov
Re: Another GCD Proof
What you showed is that any common divisor of m and n (including the greatest one) is also a common divisor of n and m - n. This does not show that the GCD of m and n is also the greatest common divisor of n and m - n.

As I said, prove that the sets of common divisors coincide. I.e., show that any divisor of m and n is also a divisor of n and m - n and vice versa. Since the sets are the same, their maximums are also the same.

You can prove a couple of facts to make this more elegant. The first fact says that any divisor of m and n is also a divisor of a linear combination of m and n. Here a linear combination of m and n is a*m + b*n for some integers a and b. Therefore, if m' and n' are two linear combinations of m and n and if d is a common divisor of m and n, then d is also a common divisor of m' and n'. Now note that n and m - n are linear combinations of m and n, and, vice versa, m and n are linear combinations of n and m - n. That would mean that the sets of divisors of these pairs are the same.