Which of the following numbers is a Fibonacci number; $(A) 75023$ $(B) 75024$ $(C) 75025$ $(D) 75026$? 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!
 A: 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   $$
A: 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}
