1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If $a,b$ come from an arbitrary set, then I'm not sure what $a=0$ and $b \bmod a$ mean. $\endgroup$ – Yuval Filmus Feb 20 at 11:21
  • $\begingroup$ @ 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. $\endgroup$ – aaag Feb 20 at 11:36
  • $\begingroup$ You have to show that the recursion can't go on forever. $\endgroup$ – Yuval Filmus Feb 20 at 11:39
  • $\begingroup$ @ 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. $\endgroup$ – aaag Feb 20 at 12:16
1
$\begingroup$

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$.

We can consider a more general situation, in which we are given a directed graph in which every vertex has at most one outgoing edge, and a starting vertex. We start at that vertex, and follow the unique outgoing edges, stopping if we ever reach a leaf. In this generality, we cannot be certain that the process always terminates. In fact, if the graph contains a directed cycle and we start with a vertex on the cycle, the process will ever terminate!

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.