Problem B. 5235. (March 2022)

B. 5235. Show that all prime numbers greater than \(\displaystyle 3\) that occur in the Fibonacci sequence are of the form \(\displaystyle 4k+1\).

(5 pont)

Deadline expired on April 11, 2022.

Sorry, the solution is available only in Hungarian. Google translation

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ú.

Statistics:

66 students sent a solution.
5 points:	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 points:	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 points:	10 students.
2 points:	6 students.
1 point:	1 student.

Problems in Mathematics of KöMaL, March 2022