Euclid's algorithm and fibonacci numbers

**sakuraxkisu** · November 26th 2012, 01:05 PM

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

$F_{0}=1$

$F_{1}=1$

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

for $n\geq 0$

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

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

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

Any help would be greatly appreciated!

**MarkFL** · November 26th 2012, 03:35 PM

a) I would use the algorithm to state:

$\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 $n-1$ times, we will find $\gcd(F_{n+1},F_{n})=\gcd(F_2,F_1)=\gcd(1,1)=1$ .

b) The first subtraction gives:

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

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

**soheilwow** · December 2nd 2012, 12:59 AM

hi
I neead an algorithm for drawing this:
Fibonacci Tornado mod 2
please help!

Thread: Euclid's algorithm and fibonacci numbers

LinkBack

Thread Tools

Display

Euclid's algorithm and fibonacci numbers

Re: Euclid's algorithm and fibonacci numbers

Re: Euclid's algorithm and fibonacci numbers

Similar Math Help Forum Discussions

[SOLVED] O(Log(n)) Algorithm for Computing Fibonacci Numbers, SICP Ex. 1.19

Euclid's Algorithm

Another GCD using Euclid's Algorithm

Euclid's algorithm

Euclid Algorithm

Search Tags