Lamé's theorem

Remarks

The proof is by induction on $N$. The last division has quotient at least $2$, because its dividend exceeds its divisor, and every earlier quotient is at least $1$. Read backwards, each number in the chain of remainders is at least the sum of the next two, so the chain dominates the Fibonacci numbers. For the digit bound, $F_{N+1} \ge \varphi^{N-1}$ with $\varphi = (1 + \sqrt 5)/2$ the golden ratio, so $N - 1 \le \log_\varphi b < 4.79 \log_{10} b$; if $b$ has $d$ digits this gives $N < 1 + 4.79\, d$, hence $N \le 5d$ since $N$ is an integer.

The bound is sharp: the pair $(F_{N+2}, F_{N+1})$ needs exactly $N$ divisions. For example, $(13, 8)$ gives $13 = 1 \cdot 8 + 5$, $8 = 1 \cdot 5 + 3$, $5 = 1 \cdot 3 + 2$, $3 = 1 \cdot 2 + 1$, $2 = 2 \cdot 1 + 0$, which is $N = 5$ divisions with $b = 8 = F_6$.

Going deeper

For a student

The theorem is one of the first results of the analysis of algorithms. It shows that computing $\gcd(a, b)$ takes $O(\log b)$ division steps, so the Euclidean algorithm runs in time polynomial in the length of the input. The same bound holds for the extended Euclidean algorithm, which performs the same divisions.