ATRACTOR

It will be greater when the number of necessary divisions to reach the greatest common divisor is smaller. Let's start with some simple examples and questions, to discover afterwards which are the worst cases.

We take two numbers, for example \(69\) and \(30\) and we apply the (division) algorithm until we have a \(0\) remainder. The quotients we get are \(2\) (\(2\) squares of side \(30\)), \(3\) (\(3\) squares of side \(9\)) and \(3\) (\(3\) squares of side \(3\)): \(69=\mathbf{2}\times30+9\), \(30=\mathbf{3}\times9+3\) and \(9=\mathbf{3}\times3+0\). Geometrically, the quotients give us the number of squares with a certain side length.

If we want to build an example which gives as a greatest common divisor the same number \(3\) and in which the quotients are \(3\), \(1\), \(4\) instead of \(2\), \(3\), \(3\), we can do it easily, starting from the end to the beginning: \(\mathbf{4}\times3+0=12\), \(\mathbf{1}\times12+3=15\), \(\mathbf{3}\times15+12=57\).

In this process, the number of quotients clearly gives the number of divisions, and the last number we reach is bigger when the chosen quotients are bigger. Therefore, if we want to know which are the smallest numbers that need that number of divisions to reach \(3\) as greatest common divisor, it suffices to apply the process to the quotients \(1\), \(1\), \(2\) (the last quotient can't be \(1\), because \(1\times x+0\) would again result in \(x\)): \(\mathbf{2}\times3+0=6\), \(\mathbf{1}\times6+3=9\), \(\mathbf{1}\times9+6=15\). The pair \((15,9)\) is the smallest one which requires \(3\) divisions to reach \(3\) as greatest common divisor.

And what would be the smallest pair which requires \(3\) divisions (without specifying what is the greatest common divisor we want to reach)? It suffices to apply the previous idea to the greatest common divisor \(1\) and to the quotients \(1\), \(1\), \(2\): \(\mathbf{2}\times1+0=2\), \(\mathbf{1}\times2+1=3\), \(\mathbf{1}\times3+2=5\); it's the pair \((5,3)\)

Similarly, the smallest pair which requires \(8\) divisions will be obtained by doing: \(\mathbf{2}\times1+0=2\), \(\mathbf{1}\times2+1=3\), \(\mathbf{1}\times3+2=5\), \(\mathbf{1}\times5+3=8\), \(\mathbf{1}\times8+5=13\), \(\mathbf{1}\times13+8=21\), \(\mathbf{1}\times21+13=34\), \(\mathbf{1}\times34+21=55\), which is \((55,34)\).
The pairs obtained this way (for the successive numbers of divisions), which are the worst from the point of view of the efficiency of the division algorithm, are the pairs of consecutive terms of the sequence \(2,3,5,8,13,21,34,55,89,144,...\), which form the terms of order bigger than \(2\) in the so-called Fibonacci sequence (its two first terms are equal to \(1\)).