[1] Euclid's Algorithm is so called because it appears in Euclid's Elements (Book 7, ca. 300 BCE). According to Knuth (1997a), it can be considered the oldest known nontrivial algorithm. The ancient Egyptian method of multiplication (exercise 1.18) is surely older, but, as Knuth explains, Euclid's Algorithm is the oldest known to have been presented as a general algorithm, rather than as a set of illustrative examples.
[2] This theorem was proved in 1845 by Gabriel Lamé, a French mathematician and engineer known chiefly for his contributions to mathematical physics. To prove the theorem, we consider pairs $(a_k ,b_k)$, where $a_k\geq b_k$, for which Euclid's Algorithm terminates in $k$ steps. The proof is based on the claim that, if $(a_{k+1},\ b_{k+1}) \rightarrow (a_{k},\ b_{k}) \rightarrow (a_{k-1},\ b_{k-1})$ are three successive pairs in the reduction process, then we must have $b_{k+1}\geq b_{k} + b_{k-1}$. To verify the claim, consider that a reduction step is defined by applying the transformation $a_{k-1} = b_{k}$, $b_{k-1} = \textrm{remainder of}\ a_{k}\ \textrm{divided by}\ b_{k}$. The second equation means that $a_{k} = qb_{k} + b_{k-1}$ for some positive integer $q$. And since $q$ must be at least 1 we have $a_{k} = qb_{k} + b_{k-1} \geq b_{k} + b_{k-1}$. But in the previous reduction step we have $b_{k+1}= a_{k}$. Therefore, $b_{k+1} = a_{k}\geq b_{k} + b_{k-1}$. This verifies the claim. Now we can prove the theorem by induction on $k$, the number of steps that the algorithm requires to terminate. The result is true for $k=1$, since this merely requires that $b$ be at least as large as $\text{Fib}(1)=1$. Now, assume that the result is true for all integers less than or equal to $k$ and establish the result for $k+1$. Let $(a_{k+1},\ b_{k+1})\rightarrow(a_{k},\ b_{k}) \rightarrow(a_{k-1},\ b_{k-1})$ be successive pairs in the reduction process. By our induction hypotheses, we have $b_{k-1}\geq {\textrm{Fib}}(k-1)$ and $b_{k}\geq {\textrm{Fib}}(k)$. Thus, applying the claim we just proved together with the definition of the Fibonacci numbers gives $b_{k+1} \geq b_{k} + b_{k-1}\geq {\textrm{Fib}}(k) + {\textrm{Fib}}(k-1) = {\textrm{Fib}}(k+1)$, which completes the proof of Lamé's Theorem.
< Previous
Next >
1.2.5  Greatest Common Divisors