If the Euclidean algorithm requires "N" steps for a pair of natural numbers "a" > "b" > 0, the smallest values of "a" and "b" for which this is true are the Fibonacci numbers "F""N"+2 and "F""N"+1, respectively. More precisely, if the Euclidean algorithm requires "N" steps for the pair "a" > "b", then one has "a" ≥ "F""N"+2 and "b" ≥ "F""N"+1. This can be shown by induction. If "N" = 1, "b" divides "a" with no remainder; the smallest natural numbers for which this is true is "b" = 1 and "a" = 2, which are "F"2 and "F"3, respectively. Now assume that the result holds for all values of "N" up to "M" − 1. The first step of the "M"-step algorithm is "a" = "q"0"b" + "r"0, and the Euclidean algorithm requires "M" − 1 steps for the pair "b" > "r"0. By induction hypothesis, one has "b" ≥ "F""M"+1 and "r"0 ≥ "F""M". Therefore, "a" = "q"0"b" + "r"0 ≥ "b" + "r"0 ≥ "F""M"+1 + "F""M" = "F""M"+2,