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

Hello, Please consider the following.

Fibonacci numbers are defined as

Step 1 - The proposition is true for n = 1

Let's apply Euclidean algorithm

This is exactly 1 step and

Step 2 - We assume that this is true for k, meaning that the Euclidean algorithm takes precisely k steps to prove that

So, the first step of the algorithm is

And from now, we need to find which is 1 and takes k steps, by induction Hypothesis. Therefore, it takes k + 1 steps to find

Step 3 - Conclusion

We have just proved that the Euclidean algorithm takes precisely n steps to prove that

Thanks