ATRACTOR

In the examples we see that the \(gcd\) is also the maximum for \(\trianglelefteq\) (which means that the \(gcd\) is a multiple of every common divisor, or that every common divisor is a divisor of the greatest common divisor).

We see now that the Euclidean algorithm always gives a common divisor which is the maximum for \(\trianglelefteq \):

when 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 common divisors of \(a\) and \(b\) are the divisors of \(r_{4}\) and \(r_{4}\) is the \(gcd\) of \(a\) and \(b\), as in the page about the Euclidean algorithm; hence all the common divisors of \(a\) and \(b\) are divisors of the \(gcd\) of \(a\) and \(b\).

It is in this sense (of maximum for \(\trianglelefteq \)) that the word "greatest" should be interpreted in "greatest common divisor"; with this meaning, it makes sense to talk about the greatest common divisor in many other situations.