This question already has an answer here:

Prove that for any given positive integer $n$,there exists a Fibonacci number divisible by $10^n$.

Another application of pigeon hole principle,and the main problem is finding the holes and pigeons.If we consider $10^n+1$ consecutive Fibonacci numbers,we can NOT claim that one of them is certainly divisible by $10^n$,but of course two of them have equal remainders mod $10^n$.
I DO KNOW this question has an elementary solution using pigeon hole principle,although the older question asked for $n=2014$ has received many advanced solutions.


marked as duplicate by Jack D'Aurizio Dec 10 '17 at 12:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Not exactly, all you can claim is that at least two of them have the same value mod $10^n$. Theoretically, they could all have value $1\mod 10^n$. This doesn't seem to be the case by the way the problem is stated, but you'll probably have to apply part of the Fibonacci recurrence to get this result. $\endgroup$ – Mark Dec 10 '17 at 10:36
  • $\begingroup$ @Mark So you mean the problem statement is not correct?! $\endgroup$ – Hamid Reza Ebrahimi Dec 10 '17 at 10:41
  • $\begingroup$ I mean the solution you had written would apply to any list of numbers with $10^n$ elements, and the thing you want to prove is false for generic lists of this type. You need to incorporate some properties of the Fibonacci numbers into your proof. $\endgroup$ – Mark Dec 10 '17 at 10:42

Three hints:

  1. Make your pigeonholes pairs of remainders module $10^n$.
  2. If you know that $F_m=F_n \mod 10^n$ and $F_{m+1}=F_{n+1}\mod 10^n$ then you can work backwards in the sequence to show that $F_{m-1}=F_{n-1} \mod 10^n$.
  3. Use the fact that $F_0=0$.

Not the answer you're looking for? Browse other questions tagged or ask your own question.