# Is there among first $100000001$ Fibonacci numbers one that ends with $0000$?

This looks like a difficult problem:

Is there among first $100000001$ Fibonacci numbers one that ends with $0000$?

(it is from a competition training; trainer suggests using pigeonhole principle)

• Then ignore the trainer. Its advice can be useful if you get stuck after you've gotten somewhere into the problem, but it's worthless for actually starting the problem. – user14972 Sep 21 '14 at 22:42
• Hint: $100000001=1\, 0000^2+1$. This is no coincidence. – Yves Daoust May 7 '15 at 7:52

Consider Fibonacci numbers $\mod 10000$. The sequence begins: $F_0=0, 1, 1, \ldots$ and continues until $F_{100000001}$. Consider the set of $100000001$ ordered pairs $(F_n, F_{n+1})$. By the pigeonhole principle, at least one of these ordered pairs occurs twice in the sequence.

Now note that the entire sequence of Fibonacci numbers $\mod 10000$ are uniquely determined by any two consecutive values, as the sequence can be constructed both forwards and backwards. ($F_n\equiv F_{n+2}-F_{n+1} \mod 10000$).

So if the ordered pair $(F_n, F_{n+1})$ occurs at both $n=m$ and $n=m+t$ for $m,t \in \mathbb{N}$, then the sequence is recurrent ($F_n \equiv F_{n+t} \mod 10000$ for all $n$).

Hence the ordered pair $(F_n=0, F_{n+1}=1)$ must also occur at both $n=0$ and $n=t$. And since $m+t$ is among the first 100000001 Fibonacci numbers, then $t$ must also be among them.

• Excellent, thanks! It looks now not that difficult at all. – VividD Sep 21 '14 at 23:03
• There's an important detail this leaves out; you show that the sequence is eventually cyclic - that is $F_n\equiv F_{n+t}\mod 10000$ for all large enough $n$ - but you then use that it holds for $n=1$. You need to notice that the map $(a,b)\mapsto (b,a+b)$ (which transitions $(F_{n-1},F_n)$ to $(F_n,F_{n+1})$) is a bijection (working mod 10000) in order to conclude that it is periodic. Otherwise, repeated applications of that map might enter a cycle, but one which does not include $(0,1)$. (e.g. like how the map $f(x)=max(x-1,0)$ acts - eventually cyclic, but not a bijection) – Milo Brandt Apr 14 '15 at 23:30

This is slightly irrelevant to what you are looking for, but I'm sure you'll be happy to know that for $n = 7500$,

f(n) = 11423965231520587047220488928656904198487186633317560797959030595738263643588305263964321080516991429937628886229555340146644442744473185460778302934743807002248109695741208782411159189994651520930091202035101269350523609417276542209682261168150544790025062794209091503702088574338650460569295592498666443239807989522593072562158640947468656887645879356201301594841872491497556389555817277508349058330498007583814270123329724353233156029127910968370052734811192660492733375394472692191584489489590970254440914222778382439339334175624660291588778456250479185237898309112318829984358216337347549014336517486496643224502773380042071174360597192343056318489287038447004730922073980870072990706067508624038407888471294048912294153491398930715643640170172837379127969101176561450586945715460276780809807889664272818316865711724985646554559305334340318994612185260719042008960311269000122672589731283419608098303367260382379660402261886574952211783683104453334281684425994447306306414660032519055079504313562694958935754118796157632978970220780288168992181699708922971417067735144929461193639081445200786881549331150381216073705417531166786634690469206418611524663013854198045284806720735273715046888704916821855277543026346215355286395854263168251068150374988851620501196943905031285049077628443804052134507022504682483293396215268186620124762379744668092166035314553541731537245946256422861852573006230492322259630342294350827184840607509969289328320360093204783447860955806396350723341261564285649453007949089154165288839814442677339344794691881510389855765582716774490000,

so there is at least one!