Unnecessarily large fibonacci

Number Theory Level 3

How many Fibonacci numbers $F_n$ divide $F_{100}$ , where $n$ is a positive integer greater than 1?

The answer is 8.

2 solutions

Discussions for this problem are now closed

Mehul Chaturvedi
Jan 25, 2015

Let $F(k)$ be a $k^{th}$ fibonacci number then no. of factors of $F(k)=$ no. of factors of $k$

Which gives us that no. of factors of $F_{100}$ =No. of factors of $100$

as $100=2^2 \times 5^2 \therefore$ no. of factors of $100=(2+1)\times(2+1)\Rightarrow 9$

hence our answer is $\Huge\Rightarrow\color{royalblue}{\boxed{9}}$

For list of fibonacci nos. click here

The number of Fibonacci factors of $F_{k}$ being equal to the number of factors of $k$ is a corollary of an even more interesting theorem that $m | n$ iff $F_{m} | F_{n}$ ! Nice problem Prashant Ramnani, although the number isn't that well chosen.

Jake Lai - 6 years, 4 months ago

The question is ill formed. The question asks for number of fibonacci numbers that divide 354...75 and not its number of factors.

Janardhanan Sivaramakrishnan - 6 years, 4 months ago

{1, 3, 5, 55, 6765, 75025, 12586269025, 354224848179261915075}

I found 8 only. I don't know which one that I missed out. I did this carefully. Anyone who is willing to do hard onto this question won't be wrong with information obtainable.

Lu Chee Ket - 6 years, 4 months ago

You are absolutely right. There are only eight distinct factors. $F_{100}$ divides $F_i$ for $i=1,2,4,5,10,20,25,50,100$ . But, $F_1=F_2=1$ . Hence, only 8 distinct factors.

Janardhanan Sivaramakrishnan - 6 years, 4 months ago

Exactly. Count the Fibonacci number 1 only once.

Lu Chee Ket - 6 years, 4 months ago

Rahul Saha
Jan 26, 2015

Use the well known fact that $\gcd(F_m,F_n)=F_{\gcd(m,n)}$

Let $m=100$ . Then it is easy to see that $n|100$ .There are only $9$ factors of $100$ . Hence the answer is $9$ .

Note that $F_1=F_2=1$ . Hence, only 8 distinct factors.

Janardhanan Sivaramakrishnan - 6 years, 4 months ago

Correct.My solution is slightly wrong then.

Rahul Saha - 6 years, 3 months ago

Unnecessarily large fibonacci

The answer is 8.

2 solutions

Discussions for this problem are now closed

0 pending reports