(m,n)=(m+kn,n)
Hello,
Let d=gcd(m,n) and d'=gcd(m+kn,n)
1st part
d divides m.
It also divides n.
So it divides every linear combination of the two, and in particular m+kn.
Therefore, d divides both m+kn and n.
We can conclude that d divides d' (because d' is the highest common factor)
2nd part
d' divides n.
d' also divides m+kn.
So it divides every linear combination of the two, and in particular m+kn+(-k)n=m.
Therefore, d' divides both m and n.
We can conclude that d' divides d.
----> d=d'