Thread: Euclid's algorithm and fibonacci numbers

1. Euclid's algorithm and fibonacci numbers

Let $\displaystyle F_{0}, F_{1}, F_{2}, F_{3},...$ be the Fibonacci numbers, defined by

$\displaystyle F_{0}=1$

$\displaystyle F_{1}=1$

$\displaystyle F_{n}=F_{n-1}+F_{n-2}$

for $\displaystyle n\geq 0$

a) Prove that for all $\displaystyle n\geq 0$ we have $\displaystyle gcd(F_{n+1}, F_{n})=1$

b) Prove that for all $\displaystyle n\geq 0$ we also have $\displaystyle gcd(F_{n+2}, F_{n})=1$

(Check what Euclid's algorithm would do if you started to compute $\displaystyle gcd(F_{n+1}, F_{n})$ or $\displaystyle gcd(F_{n+2}, F_{n})$.)

Any help would be greatly appreciated!

2. Re: Euclid's algorithm and fibonacci numbers

a) I would use the algorithm to state:

$\displaystyle \gcd(F_{n+1},F_{n})=\gcd(F_{n+1}-F_{n},F_{n})=\gcd(F_{n-1},F_{n})=\gcd(F_{n},F_{n-1})$

Thus, iterating the algorithm $\displaystyle n-1$ times, we will find $\displaystyle \gcd(F_{n+1},F_{n})=\gcd(F_2,F_1)=\gcd(1,1)=1$.

b) The first subtraction gives:

$\displaystyle \gcd(F_{n+2},F_{n})=\gcd(F_{n+1},F_{n})$ now using the result from part a) we then find:

$\displaystyle \gcd(F_{n+2},F_{n})=1$

3. Re: Euclid's algorithm and fibonacci numbers

hi
I neead an algorithm for drawing this: