Feladat:	B.4471	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Janzer Barnabás
Füzet:	2014/február, 87. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Függvények, Fibonacci-sorozat, Maradékos osztás, kongruenciák
Hivatkozás(ok):	Feladatok: 2012/szeptember: B.4471

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.   Megoldás. Legyen $f$ egy olyan polinomfüggvény, amely kielégíti a feltételt. Ekkor $f\left(F_0\right)$-nak egy pozitív prímszámnak kell lennie, legyen ez $p$. Ezek szerint a polinom konstans tagja $p$, hiszen $f\left(F_0\right)=f\left(0\right)=p$. Most vizsgáljuk meg a Fibonacci-számok $p$-vel vett osztási maradékát. Végtelen sok egymást követő Fibonacci-számból álló pár van, ám az ilyen párokban szereplő számok $p$-es maradékaira csak véges sok, legfeljebb $p^2$ lehetőség van, így létezik olyan $i$ és $j$, hogy $i<j$, $\begin{array}{c}{\displaystyle F_i\equiv F_j\left(p\right)\text{és}{F}_{i+1}\equiv F_{j+1}\left(p\right)\mathrm{.}}\end{array}$ Vegyük a legkisebb ilyen $i\mathrm{,}j$ párt, azaz $i$ legyen minimális. Tegyük fel, hogy $i\ne 0$. Mivel $F_{i-1}=F_{i+1}-F_i$ és $F_{j-1}=F_{j+1}-F_j$, azért $\begin{array}{c}{\displaystyle F_{i-1}\equiv F_{i+1}-F_i\equiv F_{j+1}-F_j\equiv F_{j-1}\left(p\right)\mathrm{.}}\end{array}$ Ekkor azonban $F_{i-1}\equiv F_{j-1}\left(p\right)$ és $F_i\equiv F_j\left(p\right)$, ami ellentmond $i$ megválasztásának. Tehát $i=0$, vagyis $F_0\equiv F_j\left(p\right)$ és $F_1\equiv F_{j+1}\left(p\right)$, amiből $\begin{array}{c}{\displaystyle F_{j+2}\equiv F_{j+1}+F_j\equiv F_{0+1}+F_0\equiv F_2\left(p\right)\mathrm{,}}\end{array}$ és ehhez hasonlóan indukcióval az is bizonyítható, hogy $\begin{array}{c}{\displaystyle F_{j+k}\equiv F_k\left(p\right)}\end{array}$ teljesül tetszőleges $k$ egész számra. Speciálisan, $F_{t\cdot j}\equiv 0\left(p\right)$ minden $t\in \text{N}$-re, ami egyben azt is jelenti, hogy végtelen sok $p$-vel osztható Fibonacci szám van. Most nézzük újra az $f$ polinomot. Először tegyük fel, hogy nem konstans. Ha a főegyütthatója negatív, akkor létezik egy $n_0$ küszöb, melyre $x>n_0$ esetén $f\left(x\right)<0$. Azaz $n_0$-nál nagyobb Fibonacci-számot behelyettesítve a helyettesítési érték negatív, ami ellentmondás. Így a főegyütthatónak pozitívnak kell lennie. Ekkor azonban létezik egy $n_1$ küszöb, melyre $x>n_1$ esetén $f\left(x\right)>p$. Azaz egy $n_1$-nél nagyobb, $p$-vel osztható Fibonacci-számot (a fent bizonyítottak szerint van ilyen) behelyettesítve a helyettesítési érték $p$-vel osztható lesz, hiszen ilyenkor minden tag osztható $p$-vel. Így az $f$ polinomfüggvény ehhez a Fibonacci-számhoz egy $p$-vel osztható, $p$-nél nagyobb prímet rendel, ami ellentmondás. Így a polinom csak konstans lehet, azaz a keresett polinomok: $f\left(x\right)=p$, ahol $p$ egy pozitív prímszám.   Megjegyzés. A megoldás első felében leírtakhoz hasonlóan igazolható az a jól ismert állítás, hogy bármely $m$ pozitív egész számra a Fibonacci-számok modulo $m$ periodikus sorozatot alkotnak. Sőt, ez az állítás nem csak a Fibonacci-sorozatra, hanem az összes rekurzív sorozatra igaz. A bizonyítás a fent leírt megoldás értelemszerű módosításával kapható.