Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 5235. feladat (2022. március)

B. 5235. Mutassuk meg, hogy a Fibonacci-sorozatban minden \(\displaystyle 3\)-nál nagyobb prímszám \(\displaystyle 4k+1\) alakú.

(5 pont)

A beküldési határidő 2022. április 11-én LEJÁRT.


Megoldás. A Fibonacci-sorozat első néhány eleme

\(\displaystyle F_1=1,\ F_2=1,\ F_3=2,\ F_4=3,\ F_5=5,\ F_6=8,\ F_7=13,\ F_8=21,\dots,\)

ezek 4-es maradéka \(\displaystyle 1,1,2,3,1,0\), majd innentől kezdve ciklikusan ismétlődik. Tegyük fel, hogy a 4-gyel osztva 3 maradékot adó \(\displaystyle p\) prímszám a Fibonacci-sorozat egy eleme, mondjuk \(\displaystyle F_n=p\). Az előbbi megfigyelésünk alapján az \(\displaystyle n\) szám 6-os maradéka 4, vagyis \(\displaystyle n=6N+4\) valamely \(\displaystyle N\) egész számra. Ismert, hogy ha \(\displaystyle k\mid \ell\), akkor \(\displaystyle F_k\mid F_{\ell}\), így speciálisan \(\displaystyle F_{3N+2}\mid F_{6N+4}\). A teljesség kedvéért ezt az állítást az alábbiakban igazoljuk is. A rekurzió ismételt alkalmazásával kapjuk, hogy

\(\displaystyle F_{6N+4}=F_{6N+3}+F_{6N+2}=2F_{6N+2}+F_{6N+1}=3F_{6N+1}+2F_{6N}=\dots=F_kF_{6N+5-k}+F_{k-1}F_{6N+4-k}.\)

Itt \(\displaystyle k=3N+2\) választással

\(\displaystyle F_{6N+4}=F_{3N+2}F_{3N+3}+F_{3N+1}F_{3N+2}\)

alapján valóban \(\displaystyle F_{3N+2}\mid F_{6N+4}\). (Az általánosabb \(\displaystyle k\mid \ell \implies F_k\mid F_\ell\) következtetés ugyanígy igazolható.)

Ha tehát \(\displaystyle F_{6N+4}=p\) prímszám, akkor \(\displaystyle F_{3N+2}\mid F_{6N+4}\) alapján \(\displaystyle F_{3N+2}=1\) vagy \(\displaystyle F_{3N+2}=p\). A Fibonacci-sorozat \(\displaystyle F_2\)-től kezdve szigorúan monoton növekedő, így \(\displaystyle F_{3N+2}<F_{6N+4}=p\) miatt csak \(\displaystyle F_{3N+2}=1\) lehet, ez azonban azt jelenti, hogy \(\displaystyle N=0\), és így \(\displaystyle F_{6N+4}=F_4=3\).

Tehát a Fibonacci-sorozatban a 3 az egyetlen 4-gyel osztva 3 maradékot adó prímszám. Így a Fibonacci-sorozatban valóban minden 3-nál nagyobb prímszám \(\displaystyle 4k+1\) alakú.


Statisztika:

66 dolgozat érkezett.
5 pontot kapott:Bényei Borisz, Chrobák Gergő, Czanik Pál, Diaconescu Tashi, Diószeghy Erzsébet, Duchon Márton, Foris Dávid, Fülöp Csilla, Horváth 530 Mihály, Jánosik Máté, Koleszár Domonkos, Kovács Alex, Lovas Márton, Mohay Lili Veronika, Móricz Benjámin, Nádor Artúr, Nagy 429 Leila, Nagy 551 Levente, Németh Márton, Simon László Bence, Somogyi Dalma, Szakács Ábel, Szanyi Attila, Tarján Bernát, Varga Boldizsár, Wiener Anna.
4 pontot kapott:Andai Márk, Bálint Béla, Balla Álmos András, Ben Gillott, Bencsik Dávid, Christ Miranda Anna, Csonka Illés, Farkas 005 Bendegúz, Farkas 512 Izabella, Kalocsai Zoltán, Kovács Benedek Noel, Kurucz Kitti, Melján Dávid Gergő, Nguyen Kim Dorka, Őrfi Ádám, Prohászka Bulcsú, Sági Mihály, Seprődi Barnabás Bendegúz, Szemlér Bálint, Tran Dávid, Világi Áron, Virág Rudolf, Zömbik Barnabás.
3 pontot kapott:10 versenyző.
2 pontot kapott:6 versenyző.
1 pontot kapott:1 versenyző.

A KöMaL 2022. márciusi matematika feladatai