ATRACTOR

Let us determine the greatest common divisor of two positive integers \(a\) and \(b\).

We begin by dividing \(a\) by \(b\): we get a quotient \(q_{1}\) and a remainder \(r_{1}\) (and the remainder is smaller than \(b\)):\[a=bq_{1}+r_{1}.\]

Any common divisor of \(a\) and \(b\) is a divisor of \(a\) and \(bq_{1}\), too, hence it is also a divisor of \(r_{1}\); therefore it is a common divisor of \(b\) and \(r_{1}\).

But every common divisor of \(b\) and \(r_{1}\) is a common divisor of \(bq_{1}\) and \(r_{1}\), too, and so it is also a divisor of \(a\); hence it is a common divisor of \(a\) and \(b\).

Conclusion: the common divisors of \(a\) and \(b\) are the divisors of \(b\) and \(r_{1}\), and so, to find the greatest common divisor of \(a\) and \(b\) it suffices to find the greatest common divisor of \(b\) and \(r_{1}\).

Now we repeat the process, dividing \(b\) by \(r_{1}\): we get a quotient \(q_{2}\) and a remainder \(r_{2}\) (and \(r_{2}\) is smaller than \(r_{1}\)):\[b=r_{1}q_{2}+r_{2}.\]

Using the same argument, we see that the common divisors of \(b\) and \(r_{1}\) are the common divisors of \(r_{1}\) and \(r_{2}\).

Going on this way, since any remainder is smaller than the previous one, we will eventually get a remainder which is equal to \(0\); for example, if the last non-zero remainder is \(r_{4}\), we have \[\begin{array}{ccl} a & = & bq_{1}+r_{1}\\ b & = & r_{1}q_{2}+r_{2}\\ r_{1} & = & r_{2}q_{3}+r_{3}\\ r_{2} & = & r_{3}q_{4}+r_{4}\\ r_{3} & = & r_{4}q_{5} \end{array}\]

The greatest common divisor of \(a\) and \(b\) is the greatest common divisor of \(b\) and \(r_{1}\), which is the greatest common divisor of \(r_{1}\) and \(r_{2}\), which is, once again, the greatest common divisor of \(r_{2}\) and \(r_{3}\), which is, finally, the greatest common divisor of \(r_{3}\) and \(r_{4}\). Since \(r_{3}\) is a multiple of \(r_{4}\), the greatest common divisor of \(r_{3}\) and \(r_{4}\) is \(r_{4}\).

In the same way we see that the greatest common divisor of \(a\) and \(b\) is always the last remainder which is different from \(0\).

The execution of the algorithm can be "followed" in a diagram of an applet (diagram of the algorithm). In this diagram, the remainder of the division of \(a\) by \(b\) is obtained by subtracting \(b\) from \(a\) the needed number of times (i.e. until we reach a number which is smaller than \(b\)).

Another applet allows us to see a geometrical interpretation of the Euclidean algorithm. The idea is that if we "remove" squares from side \(b\) in a rectangle of sides \(a\) and \(b\) \((<a)\), we are left with a rectangle with a side of length \(b\) and whose other side's length is the remainder of the division of \(a\) by \(b\).

The smaller the number of divisions needed to find the greatest common divisor is, the more efficient the algorithm will be. If you wish to see some examples and find which are the worse cases, click here.

Starting from the knowledge of these worse cases, it is possible to conclude that the number of divisions needed for the algorithm to find the greatest common divisor of two natural numbers does not exceed five times the number of digits of the smallest one. To understand how, click here.