2.1 Euclid's algorithm

The original algorithm of Euclid goes as follows. If b = 0 then d = a and we stop. Else we compute, a = b ^. w + r. We then iterate with b taking the place of a and r taking the place of b.

Since we are dealing with a, b each involving many (say N) ``digits'', each division takes N² steps as we saw earlier. Since, these divisions are iterated until we reach the GCD (which could be 1) we could iterate N times and get a total of N³ steps. This seems too large for such a fundamental operation. So we should first get a better estimate for the number of steps and then take into account the decreasing sizes of a and b.

Lemma 3   Let a > b > 0 be such that Euclid's algorithm takes exactly n steps and a is the least possible with this property. Then a = F_{n + 2} and b = F_{n + 1}, where F_n defined inductively by F₀ = F₁ = 1 and F_{n + 1} = F_n + F_{n - 1}.

The proof is related with continued fractions from which it also follows that F_n is like Cⁿ for some constant C > 1. Thus it follows that we actually need only a constant multiple of log(N) steps. It can also be noted that a and b are often of the same size (especially after the first iteration). In this case w is small so the long division takes less steps than expected.

We will study the proof of the lemma when we look at real quadratic number fields.