Euclidean algorithm worst case: why never be more than five times the number of its digits (base 10)? I read the Euclidean algorithm of Wikipedia page(https://en.wikipedia.org/wiki/Euclidean_algorithm), but I was stuck at worst-case proof. At the second paragraph, it says:

For if the algorithm requires $N$ steps, then b is greater than or equal to $F_{N+1}$ which in turn is greater than or equal to $φ^{N−1}$, where $φ$ is the golden ratio. Since $b ≥ φ^{N−1}$, then $N−1 ≤ log_φb$. Since $log_{10}φ > 1/5$, $(N − 1)/5 < log_{10}φ×log_φb = log_{10}b$. Thus, $N ≤ 5×log_{10}b$. Thus, the Euclidean algorithm always needs less than $O(h)$ divisions, where $h$ is the number of digits in the smaller number $b$.

I just can't understand why $b≥φ^{N−1}$? Is it because $F_{N+1}≥φ^{N−1}$? how to prove relation between Fibonacci number $F_{N+1}$ and the golden ratio $φ^{N−1}$?

A don't follow your notations, but I guess what you really want to show is that $$F_{N}\ge \varphi^{N-2}$$
where $\varphi$ is the golden ratio. Since $\varphi^2=\varphi+1$, one can show easily by induction on $N$ that
$$\varphi^N=F_N\varphi+F_{N-1}$$
Hence
$$\varphi^N=F_N\varphi+F_{N-1}\le F_N\varphi+F_{N}=F_N(\varphi+1)=F_N\varphi^2$$
so you get the result.
