Euclid's algorithm and fibonacci numbers

• Nov 26th 2012, 01:05 PM
sakuraxkisu
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! :)
• Nov 26th 2012, 03:35 PM
MarkFL
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\$
• Dec 2nd 2012, 12:59 AM
soheilwow
Re: Euclid's algorithm and fibonacci numbers
hi
I neead an algorithm for drawing this: