Euclidean Algorithm Resize


Number of necessary divisions

We represent by \(\left(f_{n}\right)_{n\in\mathbb{N}}\) the Fibonacci sequence \(1,1,2,3,5,8,13,21,...\)

To check that

(P) The number of necessary divisions for the algorithm to find the greatest common divisor of two natural numbers doesn't exceed five times the number of digits of the smallest

we are going to use the following results:

To see a proof of this result, click here

Let \(a\) and \(b\) be natural numbers. If \(a=b\), the algorithm gives the answer in one step, and \(1\leq5\). Note that the algorithm gives the answer after one division because \(b\) is a multiple of \(a\) and (P) is true.

If \(a<b\) and \(a\) has \(k\) digits, then \(a<10^{k}\).

If the Euclidean algorithm requires \(n\geq2\) divisions, we know by result 1 that \(a\geq f_{n+1}\). And so we must have \[10^{k}> f_{n+1}.\]

For all \(m>2\), \(f_{m}>\left(\frac{8}{5}\right)^{m-2}\).

By result 2, we have, since \(n\geq3\), \(n>2\) and result 2 is valid for \( f_{n+1}\), \(f_{n+1}>\left(\frac{8}{5}\right)^{n-1}\).

Hence, \[10^{k}>f_{n+1}>\left(\frac{8}{5}\right)^{n-1}\]and, since \(\left(\frac{8}{5}\right)^{5}>10\), we get \[10^{5k}>\left[\left(\frac{8}{5}\right)^{5}\right]^{n-1}>10^{n-1}\]

Then, \[\begin{array}{cl} & 5k>n-1\Leftrightarrow\\ \Leftrightarrow & 5k+1>n\Leftrightarrow\\ \Leftrightarrow & 5k\geq n \end{array}\] which was the result we wanted to prove.

(Note that this argument would not be applicable if we replace \(5\) with a number \(j<5\), because \(\left(\frac{8}{5}\right)^{j}<10\) if \(1\leq j<5\).)

The fact that there is no other argument which allows us to "decrease" the factor \(5\) in the given statement is shown by the fact that the calculation of the \(gcd\left(f_{6},f_{7}\right)=gcd(8,17)\) with the Euclidean algorithm requires \(5\) divisions.

The factor \(5\) is, then, the best possible in that statement.