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)?
Asked
Active
Viewed 79 times
0
-
Are you repeating this process only once? – KyleW Jul 27 '15 at 06:20
-
No, I repeat the process till a and b end up with the same value. – rkabhishek Jul 27 '15 at 06:47
1 Answers
0
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.
joriki
- 238,052