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

Az A. 550. feladat (2011. december)

A. 550. Igaz-e, hogy minden elég nagy pozitív egész szám előáll egy Fibonacci-szám és egy prímszám összegeként?

(5 pont)

A beküldési határidő 2012. január 10-én LEJÁRT.


Megoldásvázlat. A válasz: nem. Megmutatjuk, hogy végtelen sok olyan pozitív egész létezik, amely nem áll elő egy Fibonacci-szám és egy prímszám összegeként. Ehhez a Fibonacci számokat lefedjük néhány olyan számtani sorozattal, amelyek differenciái különböző prímszámok.

Jól ismert, hogy ha a Fibonacci-számoknak valamilyen pozitív egész m-mel vett maradékait vesszük, a maradékok periodikusan ismétlődnek; a periódus hosszát (jele: \pi(m) nevezik modulo m Pisano-periódusnak. (Ha valaki nem tudná, Fibonacci = Leonard Pisano.) Például a modulo 11 esetben \pi(11)=10, és az első periódus: (1,1,2,3,5,8,2,10,1,0). A példából is látszik, hogy egy periódusban többször is előfordulhat ugyanaz a maradék; pl. m>2 esetén az 1 maradék legalább háromszor előfordul, mert F-1=F1=F2=1.

p 2 3 5 11 19 31 41 61 107 181 541
\pi(p) 3 8 20 10 18 30 40 60 72 90 90

1. táblázat

A 2. táblázatban mindegyik p prímhez választunk egy modulo p maradékosztályt; ezek láthatók a jobboldali oszlopban. Az adott maradék néhány számtani sorozat mentén fordul elő, ezeket soroltuk fel a baloldali oszlopban. Az egyes sorokat úgy is olvashatjuk, hogy minden olyan esetben, amikor n a baloldali maradékosztályba tartozik, akkor Fn a jobboldali maradékosztálynak eleme.

n Fn
1 \pmod{3} 1 \pmod{2}
2 \pmod{3} 1 \pmod{2}
0 \pmod{4} 0 \pmod{3}
0 \pmod{5} 0 \pmod{5}
1 \pmod{10} 1 \pmod{11}
2 \pmod{10} 1 \pmod{11}
9 \pmod{10} 1 \pmod{11}
0 \pmod{18} 0 \pmod{19}
3 \pmod{30} 2 \pmod{31}
27 \pmod{30} 2 \pmod{31}
1 \pmod{40} 1 \pmod{41}
2 \pmod{40} 1 \pmod{41}
18 \pmod{40} 1 \pmod{41}
39 \pmod{40} 1 \pmod{41}
6 \pmod{60} 8 \pmod{61}
24 \pmod{60} 8 \pmod{61}
6 \pmod{72} 8 \pmod{107}
19 \pmod{72} 8 \pmod{107}
30 \pmod{72} 8 \pmod{107}
53 \pmod{72} 8 \pmod{107}
84 \pmod{90} 173 \pmod{181}
24 \pmod{90} 383 \pmod{541}

2. táblázat

A 2. táblázat legfontosabb tulajdonsága, hogy a baloldali oszlopban álló maradékosztályok lefedik az összes pozitív egész n-et. Ezért bármelyik Fibonacci szám beleesik legalább egy maradékosztályba a jobboldali oszlopban; a jobboldalon szereplő maradékosztályok lefedik az összes Fibonacci-számot.

A 2. táblázat birtokában már megoldhatjuk a feladatot. Legyen M=2.3.5.11.19.31.41.61.107.181.541. A kinai maradéktétel miatt van olyan A pozitív egész, amire A\equiv0\pmod{3,19}, A\equiv1\pmod{2,11,41}, A\equiv2\pmod{31}, A\equiv8\pmod{61,107}, A\equiv173\pmod{181} és A\equiv383\pmod{541} egyszerre teljesül.

Ekkor tetszőleges k,n pozitív egészekre Mk+A-Fn osztható a 2, 3, 5, 11, 19, 31, 41, 61, 107, 181, 541 prímek valamelyikével.

Az Fn+2, Fn+3, ..., Fn+541 alakú számok egy-egy 0 sűrűségű sorozatot alkotnak, míg az Mk+A számtani sorozat pozitív sűrűségű. A Fn+p alakban elő nem álló számok tehát egy pozitív alsó sűrűségű sorozatot alkotnak.

Megjegyzés. A táblázatokat könnyű számítógépes programmal ellenőrizni; ezt az Olvasóra hagyjuk.


Statisztika:

6 dolgozat érkezett.
5 pontot kapott:Ágoston Tamás, Mester Márton.
2 pontot kapott:2 versenyző.
0 pontot kapott:2 versenyző.

A KöMaL 2011. decemberi matematika feladatai