Megoldás: 16.9
Nyilván elég a sorozat elemeit mod
101000
nézni. Belátjuk, hogy ez a sorozat valahonnan periodikus. Tekintsük a sorozat egymás után következő tagjaiból alkotott párok maradékait mod
101000
. Ezek összesen
102000
félék lehetnek, tehát lesz olyan
n és
m, amelyre
fn
≡
fm
és
fn+1
≡
fm+1
mod
101000
. Ebből a sorozat képzési szabálya szerint következik, hogy
fn+2
≡
fm+2
is teljesül mod
101000
, s így az is igaz, hogy minden
i-re is
fn+i
≡
fm+i
mod
101000
. Ebből már következik állításunk, hogy a sorozat valahonnan periodikus. De az is igaz, hogy
fn-1
=
fn+1
-
fn
≡
fm+1
-
fm
=
fm-1
mod
101000
. Ebből viszont az is következik, hogy minden szóbajövő
i-re
fn-i
≡
fm-i
mod
101000
. Tehát a sorozat tisztán periodikus.
Most már csak egyetlen kis ,,cselre" van szükségünk: fel kell vennünk a sorozat
-1-edik és
-2-edik tagját is! Az egész bizonyítás során nem használtuk a kezdőértékeket, csakis a képzési szabályt. Tehát ha a sorozatot a
g0
=-1 ,
g1
=1 értékekkel indítjuk, és képzési szabálya ugyanaz marad, akkor
fn
=
gn+2
, tehát csak annyit tettünk, hogy kettővel ,,elcsúsztattuk" az eredeti Fibonacci-sorozatot. Erről a
gn
sorozatról is beláttuk tehát, hogy tisztán periodikus. De akkor végtelen sok olyan eleme van, amely
g0
=-1-et ad maradékul mod
101000
, s ezek az első kivételével
fn
sorozatnak is elemei. Ezt kellett bizonyítanunk.