Asked by Mathslover
The Fibonacci sequence
a1=1,a2=1,a3=2,a4=3,a5=5,a6=8…
is defined recursively using the formulas a1=a2=1 and an+2=an+an+1 for all n≥1. Find the greatest common divisor of a484 and a2013.
a1=1,a2=1,a3=2,a4=3,a5=5,a6=8…
is defined recursively using the formulas a1=a2=1 and an+2=an+an+1 for all n≥1. Find the greatest common divisor of a484 and a2013.
Answers
Answered by
Steve
It has been proven that
gcd(F<sub>m</sub>,F<sub>n</sub>) = F<sub>gcd(m,n)</sub>
So,
gcd(F<sub>484</sub>,F<sub>2013</sub>) = F<sub>gcd(484,2013)</sub> = F<sub>11<sub> = 89
gcd(F<sub>m</sub>,F<sub>n</sub>) = F<sub>gcd(m,n)</sub>
So,
gcd(F<sub>484</sub>,F<sub>2013</sub>) = F<sub>gcd(484,2013)</sub> = F<sub>11<sub> = 89