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.
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.
Claim: For every pair of positive natural numbers (m, n), if m >= n, then gcd(m, n) = gcd(n, m-n)
Thanks in advance
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?
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.