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=F₁=F₂=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 F_n a jobboldali maradékosztálynak eleme.

n	F_n
$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-F_n osztható a 2, 3, 5, 11, 19, 31, 41, 61, 107, 181, 541 prímek valamelyikével.

Az F_n+2, F_n+3, ..., F_n+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 F_n+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

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

Már regisztráltál?
Új vendég vagy?