 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".