I was going over a process that tries to show the euclidean algorithm distilling it to a series of movements across the number line. The basic movements are measured by the $2$ numbers that we are interested in each time and other movements are built on top of that.
Example for numbers $133$ and $85$ (I am sorry for the inaccuracy of the diagram, didn’t know of any good tool for such a case)
Now if you notice this process essentially at this point moves around at intervals of $11$ steps and if we continue back and forth with moves like that it will eventually reach $1$.
Also $1$ is the greatest common divisor of both numbers.
If we take two different examples:
E.g. $8$ and $4$ we would have:
This essentially ends up with an infinite loop as we can see from the diagram
Also for $91$ and $49$ we would have:
Now from there on the algorithm does not enter a loop but can only move in multiples of $7$ which is also the GCD of $91$ and $49$
So my questions are:
- how do we know when the process stops? In the first case it stops to $1$ in the latter goes in an infinite loop but the GCD(8,4) = 4 and in the last it does not go in an infinite loop but the last decrement is $7$.
- what would be an intuitive explanation of the process?