# Fibonacci/Euclidean Algorithmn proof

Printable View

• November 7th 2007, 01:48 PM
padsinseven
Fibonacci/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
• November 7th 2007, 05:17 PM
ThePerfectHacker
$u_{n+1} = 1\cdot u_n + u_{n-1}$
$u_{n} = 1\cdot u_{n-1}+u_{n-2}$
...

Keep on going until you reach the final step.