# Euclidean algorithm efficiency.

According to Euclides' algorithm, suppose that $$a \ge b \gt 0$$, we have

$$a = bq_0 + r_0 \qquad 0 \lt r_0 \lt b$$ $$b = r_0q_1 + r_1 \qquad 0 \lt r_1 \lt r_0$$ $$r_0 = r_1q_2 + r_2 \qquad 0 \lt r_2 \lt r_1$$ $$.$$ $$.$$ $$r_{i-2} = r_{i-1}q_i + r_i \qquad 0 \lt r_i \lt r_{i-1}$$ $$r_{i-1} = r_iq_{i+1} + r_{i+1} \qquad r_{i+1} = 0$$

prove that $$b \gt 2^{i/2}$$

I haven't been able to prove this even though it seems quite logical.

• Hint: prove something like $r_j > 2r_{j+2}$. Commented Jun 21, 2019 at 16:32
We have: $$r_k=r_{k+1}q_{k+2}+r_{k+2} \geqslant r_{k+1}+r_{k+2}$$ since $$r_j>r_{j+1} \implies q_j \geqslant 1$$. We then have: $$b \geqslant r_0+r_1 \geqslant 2r_1+r_2 \geqslant 3r_2+2r_3 \geqslant \ldots \geqslant F_{i+2}r_i+F_{i+3}r_{i+1} \geqslant F_{i+2}(1)+0 = F_{i+2}$$ where $$F_n$$ is the $$n^{th}$$ Fibonacci number. Now, we only need to show that $$F_{i+2} > 2^{i/2}$$ for $$i \in \mathbb{N}_0$$. We can see that this trivially holds true for $$i=0,1$$. Now, let this hold true for $$i=k,k+1$$. Then- $$F_{k+2}=F_{k+1}+F_k \geqslant 2F_k > 2 \cdot 2^{{(k-2)}/{2}}=2^{k/2}$$ Thus, by induction hypothesis, we are done. Note that the quotient between consecutive Fibonacci Numbers approaches $$\phi=1.618...$$ but the ratio required to solve this problem is only $$\sqrt{2}=1.414...$$ which means that our result can be made much stronger.