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

Printable View

- Nov 7th 2007, 12:48 PMpadsinsevenFibonacci/Euclidean Algorithmn proof
Let u sub n be the nth Fibonacci number. Prove that the Euclidean algorithm takes precisely n steps to prove that gcd(u sub n+1, u sub n)=1

- Nov 7th 2007, 04:17 PMThePerfectHacker
$\displaystyle u_{n+1} = 1\cdot u_n + u_{n-1}$

$\displaystyle u_{n} = 1\cdot u_{n-1}+u_{n-2}$

...

Keep on going until you reach the final step.