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

Following are the answer to this question:

Explanation:

According to Eucharistic algorithm:

`gcd(un+1,un) = gcd (un+1-un, un)`

`= gcd (un , un-1)`

so many recursions following

It was the first two the Fibonacci 1,1 numbers

`gcd(un+1, un) = gcd(1,1) = 1 \\\\ from 1 =1 \text{and euclidean principle} \\\\?gcd (un+1,un ) = 1`