A B. 4228. feladat (2009. december)

B. 4228. A p_n sorozatot rekurzívan definiáljuk. Legyen p₁=2 és p_n+1 legyen p₁p₂...p_n+1 legnagyobb prímosztója. Szerepel-e a sorozatban a 11?

(5 pont)

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

Megoldás. A sorozat minden eleme prímszám. Nyilván $\displaystyle p_2=3$, $\displaystyle p_3=7$, és a sorozatban minden prímszám legfeljebb egyszer szerepel, hiszen a sorozat minden eleme relatív prím az azt megelőző elemekhez. Tegyük fel, hogy a sorozatban szerepel a 11, ekkor valamely $\displaystyle n\ge 3$ esetén a $\displaystyle p_1p_2\ldots p_n+1$ szám prímosztói között csak az 5 és a 11 szerepelhet, hiszen a többi 11-nél kisebb prímhez biztosan relatív prím. Ez a szám tehát $\displaystyle 5^a\cdot11^b$ alakba írható alkalmas $\displaystyle a,b$ nemnegatív egész számokkal. Erre a számra teljesül, hogy

$\displaystyle 5^a\cdot11^b-1=p_1p_2\ldots p_n$

osztható 2-vel, 3-mal és 7-tel is, de nem osztható 4-gyel. Mivel $\displaystyle 5^a$ néggyel osztva 1 maradékot ad, $\displaystyle 11^b$ nem adhat 1 maradékot, hiszen akkor $\displaystyle 5^a\cdot11^b$ is 1 maradékot adna. Ezért $\displaystyle b$ csak páratlan szám lehet. Ekkor $\displaystyle 11^b$ hárommal osztva 2 maradékot ad. Ahhoz, hogy $\displaystyle 5^a\cdot11^b$ hárommal osztva 1 maradékot adjon, az szükséges, hogy $\displaystyle 5^a$ hárommal osztva 2 maradékot adjon, ami csak úgy lehet, ha $\displaystyle a$ is páratlan. Ekkor viszont alkalmas $\displaystyle u$ egész számmal $\displaystyle 5^a\cdot11^b=55u^2$. Mivel 55 héttel osztva 6 maradékot ad, a négyzetszámok pedig 0, 1, 2, vagy 4 maradékot adnak, könnyen ellenőrizhető, hogy $\displaystyle 55u^2-1$ nem lehet osztható 7-tel. Ezért a sorozatban nem szerepelhet a 11.

Statisztika:

38 dolgozat érkezett.
5 pontot kapott:	Ágoston Péter, Ágoston Tamás, Boér Lehel, Cséke Balázs, Damásdi Gábor, Dudás 002 Zsolt, Éles András, Énekes Péter, Gyarmati Máté, Hajnal Péter János, Janzer Olivér, Karl Erik Holter, Kiss 902 Melinda Flóra, Márkus Bence, Máthé László, Mester Márton, Mészáros András, Nagy Balázs, Németh Bence, Neukirchner Elisabeth, Perjési Gábor, Popper Dávid, Somogyi Ákos, Szabó 928 Attila, Weisz Ágoston, Weisz Gellért, Zsakó András.
4 pontot kapott:	Nagy Róbert.
3 pontot kapott:	5 versenyző.
2 pontot kapott:	2 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2009. decemberi matematika feladatai