Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4471. (September 2012)

B. 4471. Find those polynomial functions of integer coefficients that assign a positive prime number to every Fibonacci number. (The sequence Fn of Fibonacci numbers is defined by the recurrence relation Fn=Fn-1+Fn-2 with seed values F0=0, F1=1.)

(6 pont)

Deadline expired on October 10, 2012.


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

Megoldás. Legyen f(x) egy ilyen polinomfüggvény, f(0)=f(F0)=p. Tegyük fel, hogy valamely Fn Fibonacci-szám osztható p-vel. Mivel f egész együtthatós és konstans tagja f(0), látható hogy p\mid F_n\mid f(F_n)-f(0)=f(F_n)-p. Ennélfogva p osztója az f(Fn) függvényértéknek, vagyis f(Fn)=p. Megmutatjuk, hogy végtelen sok olyan n természetes szám van, melyre p\mid F_n teljesül. Mivel a Fibonacci-számok F1=F2 kivételével mind különbözőek, ebből következik, hogy az f(x) polinomfüggvény végtelen sok helyen veszi fel a p értéket, ami azt jelenti, hogy az f(x)-p polinomfüggvénynek végtelen sok gyöke van, vagyis azonosan 0, hiszen egy k-adfokú polinomfüggvénynek legfeljebb k különböző gyöke lehet. Innen pedig már látszik, hogy a feladat megoldásai azok az f(x)=c konstans függvények, ahol c értéke pozitív prímszám, ami végtelen sok megoldást jelent.

Már csak a Fibonacci-sorozatra vonatkozó állításunkat kell igazolni. Ehhez tekintsük a sorozat elemeit modulo p. Az (Fk,Fk+1) számpárok modulo p legfeljebb p2 különböző értéket vehetnek fel, vagyis kell legyenek olyan k<m indexek, melyekre F_k\equiv F_m \pmod{p} és F_{k+1}\equiv F_{m+1} \pmod{p} is teljesül. Ekkor persze Fk+2=Fk+1+Fk és Fm+2=Fm+1+Fm miatt F_{k+2}\equiv F_{m+2} \pmod{p}. A rekurziót visszafelé alkalmazva pedig Fk-1=Fk+1-Fk és Fm-1=Fm+1-Fm alapján kapjuk, hogy F_{k-1}\equiv F_{m-1} \pmod{p} (feltéve, hogy k>0). Innen indukcióval nem nehéz belátni, hogy az m-k=n jelöléssel minden i természetes számra teljesül F_{n+i}\equiv F_i\pmod{p}, amiből adódik, hogy az F_0,F_n,F_{2n},F_{3n},\ldots Fibonacci-számok mind oszthatók p-vel.


Statistics:

44 students sent a solution.
6 points:Ágoston Péter, Balogh Tamás, Bogár Blanka, Csernák Tamás, Fonyó Viktória, Forrás Bence, Géczi Péter Attila, Havasi 0 Márton, Ioan Laurentiu Ploscaru, Janzer Barnabás, Janzer Olivér, Kabos Eszter, Kaprinai Balázs, Kúsz Ágnes, Maga Balázs, Makk László, Nagy Róbert, Petrényi Márk, Sagmeister Ádám, Sárosdi Zsombor, Simon 047 Péter, Somogyvári Kristóf, Szabó 789 Barnabás, Szabó 928 Attila, Tossenberger Tamás, Vályi András, Varnyú József, Zilahi Tamás.
5 points:Dinev Georgi, Homonnay Bálint, Seress Dániel, Tardos Jakab, Venczel Tünde.
4 points:5 students.
1 point:1 student.
0 point:5 students.

Problems in Mathematics of KöMaL, September 2012