Which of the following numbers is a Fibonacci number; $(A) 75023$ $(B) 75024$ $(C) 75025$ $(D) 75026$?

Question

This question appeared in one of the mathematical societies exams in Saudi Arabia.

• No calculator is allowed.

• The required time to solve one question is $4$ minutes (on average).

• There is only one correct choice to each question.

Which of the following is a Fibonacci number?

$(A) 75023$ $(B) 75024$ $(C) 75025$ $(D) 75026$

I thought about:

Any number $n$ can be a Fibonacci number if and only if at least one of $5n^2+4$ or $5n^2-4$ is a perfect square.

But without using a calculator, how can I proceed? Is there this statement useful to solve this problem? Can we solve it using another useful statement?

The Correct Option:

$(C) 75025$ which is the $25^\text{th}$ Fibonacci number, I used WA to check.

---

Any help would be really appreciated. THANKS!

Answer 1

From the last part of the section WICK

If you know two F numbers in a row, you can double the index $$ F_{2n-1} = F_{n-1}^2 + F_n^2 $$ $$ F_{2n} = 2F_{n-1} F_n + F_n^2 $$ $$ $$ $$ $$ $$ F_4 = 3, F_5 = 5 $$ so $$ F_6 = 8, F_7 = 13 $$

doubling $$ F_{13} = 8^2 + 13^2 = 233 $$ $$ F_{14} = 2\cdot 8 \cdot 13 + 169 = 208 + 169 = 377 $$

back up one, $$ F_{12} = 377-233 = 144 $$

$$ F_{25} = 144^2 + 233^2 =20736+54289 = 75025 $$

Answer 2

It is easy to compute by hand $F_n \bmod 25$. As explained in this answer, this sequence is periodic, but the first values, given in the table below, will suffice. Now, the given numbers (A)-(D) are respectively equal to $-2$, $-1$, $0$, $1$ modulo $25$. For $3\leqslant n \leqslant 44$, only one of these four values occurs in the table: $F_{25} \equiv 0 \bmod 25$. Thus the solution is (C). \begin{array}{c} \hline 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\ \hline 0&1&1&2&3&5&8&-12&-4&9&5&-11&-6&8&2\\ \hline \\ \hline 15&16&17&18&19&20&21&22&23&24&\color{red}{25}&26&27&28&29\\ \hline 10&12&-3&9&6&-10&-4&11&7&-7&\color{red}0&-7&-7&11&4 \\ \hline \\ \hline 30&31&32&33&34&35&35&37&38&39&40&41&42&43&44\\ \hline -10&-6&9&3&12&-10&2&-8&-6&11&5&-9&-4&12&8\\ \hline \end{array}