contestada

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

Respuesta :

Answer:

Following are the answer to this question:

Step-by-step explanation:

According to Eucharistic algorithm:

[tex]gcd(un+1,un) = gcd (un+1-un, un)[/tex]  

                        [tex]= gcd (un , un-1)[/tex]

so many recursions following  

It was the first two the Fibonacci 1,1 numbers  

[tex]gcd(un+1, un) = gcd(1,1) = 1 \\\\ from 1 =1 \text{and euclidean principle} \\\\?gcd (un+1,un ) = 1[/tex]