Termination state while subtracting two numbers

Question

Let a and b be positive integers such that $a > b$. Then I replace $a$ with $a-b$.

If I repeat this process, how do I prove that both numbers will be equal to x such that x=gcd(a, b)?

Answer 1

With $x=gcd(a,b)$, write $a=rx$ and $b=sx$. Clearly the process will only ever produce multiples of $x$, so you can factor out $x$ and show that applying the process to the positive coprime integers $r$ and $s$ will necessarily end at $1$. This you can do by assuming the opposite (that it ends at $0$) and deriving a contradiction to the fact that $r$ and $s$ are coprime.