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

Problem A. 598. (October 2013)

A. 598. Denote by un the nth Fibonacci number (u1=u2=1, un+1=un+un-1). Prove that if a,b,c>1 are integers such that a divides ub, b divides uc and c divides ua, then 5 divides a, b and c, or 12 divides a, b and c.

(5 pont)

Deadline expired on November 11, 2013.


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

Megoldásvázlat. Tetszőleges m-re az m-mel osztható Fibonacci-számok indexei egy számtani sorozatot alkotnak, amelyben a 0 is szerepel; jelöljük ennek differenciáját dm-mel. Könnyű ellenőrizni, hogy d2=3, d3=4, d4=6, d5=5, d6=12 és d12=12.

Ha a,b,c között van 5-tel osztható, mondjuk 5|a, akkor


5\big|a\big|u_b ~\Rightarrow~
5=d_5\big|b\big|u_c ~\Rightarrow~ 
5=d_5\big|c,

vagyis a,b,c mindegyike osztható 5-tel.

Ha a,b,c között van 3-mal osztható, mondjuk 3|a, akkor


3\big|a\big|u_b ~\Rightarrow~ 
4=d_3\big|b\big|u_c ~\Rightarrow~ 
6=d_4\big|c\big|u_a ~\Rightarrow~ 
12=d_6\big|a\big|u_b ~\Rightarrow~ 
12=d_{12}\big|b\big|u_c ~\Rightarrow~ 
12=d_{12}\big|c\big|u_a,

vagyis a,b,c mindegyike osztható 12-vel.

Ha a,b,c között van páros, mondjuk 2|a, akkor 2|a|ub miatt 3=d2|b, tehát a számok között van 3-mal osztható is, az előző bekezdés szerint tehát a,b,c is osztható 12-vel.

A továbbiakban feltételezzük, hogy abc legkisebb prímosztója p\ge7. Az a,b,c szerepének szimmetriája miatt feltehetjük, hogy p|a.

A dp szám osztója az úgynevezett \pi(p) Pisano-periódusnak. Az is ismert, hogy ha p prím és p\ne5, akkor \pi(p)|p2-1, tehát dp|\pi(p)|p2-1 és így

p|udp|up2-1.

(Általánosabban, ha p\equiv\pm1\pmod5, akkor dp|p-1, p\equiv\pm2\pmod5 esetén pedig dp|p+1.)

Másrészt

p|a|ub,

amiből

p|gcd(up2-1,ub)=ugcd(p2-1,b).

A b szám mindegyik prímosztója p, vagy legalább p+2, ezek egyike sem osztója p2-1=(p-1)(p+1)=nek. Ezért ugcd(p2-1,b)=u1=1, azaz p|1, ami ellentmondás. Ez az eset tehát nem lehetséges.


Statistics:

12 students sent a solution.
5 points:Fehér Zsombor, Maga Balázs, Nagy Bence Kristóf, Simon 047 Péter, Szabó 789 Barnabás, Szőke Tamás, Tossenberger Tamás, Williams Kada.
1 point:1 student.
0 point:3 students.

Problems in Mathematics of KöMaL, October 2013