# Existence of a Fibonacci number divisible by $10^n$ [duplicate]

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'AurizioDec 10 '17 at 12:10

• 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. – Mark Dec 10 '17 at 10:36
• 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. – Mark Dec 10 '17 at 10:42
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$.