Question

Let un be the nth Fibonacci number. Prove that the Euclidean algorithm takes precisely n steps to prove that gcd(un+1, un) = 1.

Answer 1

Hello, Please consider the following.

Fibonacci numbers are defined as

$u_0=1\\\\u_1=1\\\\u_{n+2}=u_{n+1}+u_{n} \ for \ n\geq 0$

Step 1 - The proposition is true for n = 1

$GCD(u_2,u_1) ?$

Let's apply Euclidean algorithm

$u_1=1, u_2=2\\\\u_2=2\times u_1+0 = 2 \times 1 +0$

This is exactly 1 step and $GCD(u_2,u_1) =1$

Step 2 - We assume that this is true for k, meaning that the Euclidean algorithm takes precisely k steps to prove that $GCD(u_{k+1},u_{k})=1$

$u_{k+2}=u_{k+1}+u_k \ and \ 0 < u_k < u_{k+1}$

So, the first step of the algorithm is

$u_{k+2}=u_{k+1}\times 1 +u_{k}$

And from now, we need to find $GCD(u_{k+1},u_k)$ which is 1 and takes k steps, by induction Hypothesis. Therefore, it takes k + 1 steps to find $GCD(u_{k+2},u_{k+1})=1$

Step 3 - Conclusion

We have just proved that the Euclidean algorithm takes precisely n steps to prove that $GCD(u_{n+1},u_{n})=1$

Thanks