MacTutor
Connections with the Fibonacci Sequence
The Euclidean Algorithm as some curious connections with the Fibonacci sequence
If you apply the Euclidean Algorithm to a pair of successive terms of the sequence the quotients are always +1 and the remainder is the next term down in the sequence.
As a result the algorithm takes long to find the HCF of a pair of successive Fibonacci numbers (the HCF is 1) than any pair of similar size. (This was investigated by Lagny.)
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
in which each term is the sum of the two preceding ones.
If you apply the Euclidean Algorithm to a pair of successive terms of the sequence the quotients are always +1 and the remainder is the next term down in the sequence.
As a result the algorithm takes long to find the HCF of a pair of successive Fibonacci numbers (the HCF is 1) than any pair of similar size. (This was investigated by Lagny.)