Anonymous
Anonymous asked in Science & MathematicsMathematics · 2 months ago

Prove gcd(a,b)=gcd(a-b,b)?

Relevance
• oyubir
Lv 6
2 months ago

gcd(a,b)=k ⇒ ∃ a',b', a=k×a', b=k×b'

Then a-b=k(a'-b'). So k is also a common factor of a-b and b. Which only proves that gcd(a-b,b) ≥ k (a multiple of k could also be the gcd. There could be another factor of a-b and b which was not factor of a and b).

So, let assume ∃ k'>k, c, b'' such as a-b=k'×c, b=k'×b''

then a=k'c + k'b'' = k'(c+b''). Which means that k' is a factor of both a and b. Which is impossible since k'>k, the biggest possible common factor of both a and b.

Another way to put it:

∃ a',b', a=gcd(a,b)a', b=gcd(a,b)b'. Then a-b=gcd(a,b)(a'-b'). So a-b and b share the same common factor gcd(a,b). So gcd(a-b,b)≥gcd(a,b)

∃ c'', b'', a-b=gcd(a-b,b)c'',  b=gcd(a-b,b)b''. Then a=a-b+b = gcd(a-b,b)(c''+b''). So a-b and a share common factor gcd(a-b,b). So gcd(a,b)≥gcd(a-b,b).

gcd(a-b,b)≥gcd(a,b) and gcd(a,b)≥gcd(a-b,b) implies gcd(a,b)=gcd(a-b,b)