# Euclidean algorithm and well define ness on the underlying set

Euclidean algorithm is given below:

gcd($$a$$,$$b$$):

if $$a=0$$, return $$b$$

otherwise, return gcd($$b \bmod a$$, $$a$$)

Let us first argue that the algorithm terminates. The reason is that each time the number is decreasing, and there is a well-ordering defined on the set from which number $$a$$ and $$b$$ are defined.

Question: What if the well-ordering is not defined on the set from which elements $$a$$ and $$b$$ are coming? In that case can we say that algorithm will take finite time? To me it appears no, but the reasoning is not clear to me.

• If $a,b$ come from an arbitrary set, then I'm not sure what $a=0$ and $b \bmod a$ mean. – Yuval Filmus Feb 20 '19 at 11:21
• @ Yuval Filmus That is not clear to me also. I am only trying to figure where exactly in the proof of the above algorithm well definess comes. – Shiv Feb 20 '19 at 11:36
• You have to show that the recursion can't go on forever. – Yuval Filmus Feb 20 '19 at 11:39
• @ Yuval Filmus I know but the only argument I have seen in the textbooks or in other places is that either $a$ will decrease in each set or $b$ will decrease in each step. Which does not seems to me complete. – Shiv Feb 20 '19 at 12:16

We can think of the GCD algorithm as taking place inside a directed graph. The vertices of the graph are all pairs $$(a,b)$$, where $$a,b \geq 0$$. If $$a \neq 0$$, then there is an edge from $$(a,b)$$ to $$(b \bmod a, a)$$. The algorithm starts at some vertex $$(a,b)$$, follows the unique outgoing edges, until (hopefully) reaching a leaf $$(0,b)$$, at which point it outputs $$b$$.
Consider for example the graph on $$1,2,3$$ with edges $$1\to 2$$, $$2 \to 3$$, $$3 \to 1$$. On this graph, the iterative process will never terminate.
There is another reason for the process to not terminate: there might be an infinite directed path. For example, consider the directed graph on the integers in which the edges are $$a \to a+1$$. This graph contains no cycles, but nevertheless the process does not terminate.
To show that the GCD algorithm always terminates, we define a potential function $$\phi$$ on the vertices by $$\phi(a,b) = a$$. If $$(a,b) \to (b \bmod a,a)$$ then $$\phi(b \bmod a,a) = b \bmod a < a = \phi(a,b).$$ Therefore the potential decreases. Since the potential is always a natural number, and these are well-ordered, it cannot decrease forever, and therefore the algorithm necessarily terminates.
To finish, let me mention the Collatz conjecture. Consider the directed graph on the positive integers in which the edges are $$2n \to n$$ and $$2n+1 \to 3n+2$$ for all $$n \geq 1$$. The Collatz conjecture states that the process considered above always terminates, no matter what the starting vertex is. The conjecture is suspected to be true, but nobody knows how to prove it.