Feladat: N.164 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Baharev Ali ,  Bérczi Gergely ,  Csóka Endre ,  Gerbicz Róbert ,  Gyenes Zoltán ,  Győri Nikolett ,  Hegedűs Péter ,  Horváth Gábor ,  Juhász András ,  Kun Gábor ,  Lippner Gábor ,  Lukács László ,  Mecz Balázs ,  Naszódi Gergely ,  Pataki Péter ,  Székelyhidi Gábor ,  Végh A. László ,  Zábrádi Gergely 
Füzet: 1998/október, 422 - 423. oldal  PDF file
Témakör(ök): Fibonacci-sorozat, Nehéz feladat
Hivatkozás(ok):Feladatok: 1998/február: N.164

Van-e olyan eleme a Fibonacci-sorozatnak, amelynek tízes számrendszerbeli alakja 6 darab 9-es számjegyre végződik?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Jelölje fi a Fibonacci-sorozat i-edik elemét, azaz f0=f1=1, fn+2=fn+1+fn.
A Fibonacci-sorozat értelemszerűen kiterjeszthető negatív indexekre is (f-1=0, f-2=1, f-3=-1 stb).
Bebizonyítjuk a következőt: (fn) m szerint vett maradékai periodikusak (minden m>1-re).
Tekintsük ugyanis az (fi,fi+1) (iZ) rendezett párokat modulo m. Közülük véges sok, legfeljebb m2 különböző lehetséges, így létezik olyan i<j, amelyre fifj és fi+1fj+1 (mod m). Innen nyilván fi-1fj-1 és fi+2fj+2 adódik a rekurzióból, ezért teljes indukcióval azt kapjuk, hogy (fn) az m szerint vett maradékra nézve periodikus (mindkét irányban!) a j-i periódussal.
Ekkor végtelen sok pozitív j van, amelyre  -1=f-3fj (mod 1000000), és j>0 esetén fj>0; vagyis fj a 10-es számrendszerben felírva 6 darab 9-esre végződik.