Prove that for positive integers, m,n; gcd(m,n) = gcd(m−n,n)
I assume w.l.o.g. that m >= n
Let’s define a and b as follows:
Let’s subtract second equation from the first:
Statement “gcd(m-n,n) = gcd(m,n)” is equivalent to
"gcd ((a-b)* gcd(m,n), n) = gcd(m,n)",
which is true if (a-b) is not a multiple of any of divisors of n apart from 1.
Let’s assume (a-b) is a multiple of c, such that c != 1 && n is divisible by c.
Because n is divisible by c and gcd(m,n) is a multiple of all the common divisors of m and n, m must not be divisible by c, implying that a must not be divisible by c, which leads to contradiction:
(a-b) must be divisible by c and be a whole number, but:
because a subtraction of a whole number from a fraction is a fraction,
Thus, a-b is not a multiple of c and gcd(m,n) = gcd(m-n,n)