I'm new to number theory, I just understood the proof of Euclidean Algorithm and how it cleverly uses the fact that $\mathrm{gcd}(a,b) = \mathrm{gcd}(b,r)$ repeatedly, where $a$ is the dividend, $b$ is the divisor and $r$ is the remainder.
Although one thing, I still don't understand is that, why do we always eventually end up with a zero anyway? What's the logic behind this?
Best Answer
Assuming $a$ and $b$ are positive and $a>b$, by definition, $r$ is less than $b$. Then $b<a$ and $r<b$, so you have smaller numbers than you started with. If $a<b$, then just switch $a$ and $b$. If $a=b$, then $\gcd(a,\,b)=a=b$. Since $b$ and $r$ are still non-negative (also by definition), the only possibility is to go to zero. The numbers are getting smaller and remaining non-negative.