Why does the Euclidean algorithm always terminate? Why does the Euclidean algorithm always terminate? Can we make this effective by bounding the number of steps it takes in terms of the original integers?
 A: Yes there is a bound. It is used in computational mathematics. If $a$ and $b$ are integers ($a\ge b\ge1$) and the euclidean alg. required $n+1$ operations then you have $n+1 \lt 5\log_{10}b$.
Moreover the algorithm must terminate in a finite number steps because in each step you have a remainder that is strictly less than its predecessor.  So if it don't terminate then the set of all remainders will not have the minimal element, but this is an absurdum.(We are in $\mathbb N$).
A: If you take two steps on the Euclidean algorithm, you have halved the size of the larger number.
$$\begin{align} 
a,b &\to b, c \;(\equiv a \bmod b)\\[3ex]
b\le a/2 &\implies c<b \le a/2 \\
b>a/2 &\implies c=a-b < a/2\\[3ex]
b,c &\to c,d\;(<c) \quad\square
\end{align}$$
So the process terminates in at most $2\log_2 a$ steps.
A: It always terminates because at each step one of the two arguments to $\gcd({}\mathbin\cdot{},{}\mathbin\cdot{})$ gets smaller, and at the next step the other one gets smaller.  You can't keep getting smaller positive integers forever; that is the "well ordering" of the natural numbers.  As long as neither of the two arguments is $0$ you can take it one more step, but it can't go on forever, so you have to reach a  point where one of them is $0$, and then it stops.
As for bounds, a very crude and easily established upper bound on the number of steps is the sum of the two arguments. One of the arguments is reduced by at least $1$ at each step, and you can't reduce $n$ repeatedly by $1$ more than $n$ times without bringing it to $0$.
The worst case is $\gcd(m,n)$ where the ratio of $m$ to $n$ is the ratio of two consecutive Fibonacci numbers.  For now I'll leave the proof of that as an exercise.
A: Consider the following invariant of the algorithm: take $|a|+|b|$.
Assume $a>b$. The algorithm can be defined as follows: replace $(a,b)$ with $(a-b,b)$ if $a-b>b$ and $(b,a-b)$ if $a-b\leq b$. When one of the elements is zero, return the other element. In this procedure $|a|+|b|$ always gets smaller, but it has a minimum of $1$. Thus it terminates
A: This is a case of "infinite descent".
An iteration of the algorithm transforms a pair $(a,b)$ with $a>b\ge0$ into another pair $(a',b')$ with $a'>b'\ge0$, and also $a'<a$ (not $a'\le a$). So unavoidably you transform a problem in another problem of the same type with smaller arguments, and you will reach $0$ after a finite number of steps.
For a discussion of the number of steps, see https://en.wikipedia.org/wiki/Euclidean_algorithm#Number_of_steps.
A: If you take gcd (x,0), the process doesn't terminate. In effect because r=x
This causes quite the show if you're using a physical adding machine
https://www.alltechbuzz.net/mechanical-calculator-dividing-by-zero/
(Link shows adding machine stuck in an endless loop)
So if the process never ends, you would conclude one of the integers in the Euclidean Algorithm would have to be 0.
