 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.