 Therefore, "a" = "q"0"b" + "r"0 ≥ "b" + "r"0 ≥ "F""M"+1 + "F""M" = "F""M"+2,
which is the desired inequality.This proof, published by Gabriel Lamé in 1844, represents the beginning of computational complexity theory, and also the first practical application of the Fibonacci numbers.This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10).