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

A B. 4241. feladat (2010. január)

B. 4241. Legyen p1=2, és n\ge1 esetén jelölje pn+1 a np_1^{1!}p_2^{2!}\ldots p_n^{n!}+1 szám legkisebb prímosztóját. Igazoljuk, hogy a p1,p2,... sorozatban minden prímszám előfordul.

(5 pont)

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


Megoldás. Tegyük fel, hogy nem igaz az állítás, és jelölje \(\displaystyle q\) a legkisebb prímszámot, amely nem fordul elő a sorozatban. Válasszuk a \(\displaystyle c\) egész számot olyan nagynak, hogy a \(\displaystyle p_1,p_2,\ldots,p_{cq}\) számok között szerepeljen az összes \(\displaystyle q\)-nál kisebb prímszám. Ekkor a

\(\displaystyle t= p_1^{1!}p_2^{2!}\ldots p_{cq}^{(cq)!}\)

szám nem osztható \(\displaystyle q\)-val, viszont osztható az összes \(\displaystyle q\)-nál kisebb prímszámmal. Ezen felül minden \(\displaystyle cq+1\le i\le cq+q-1\) esetén

\(\displaystyle p_i^{i!}=(p_i^{q-1})^{\frac{i!}{q-1}}\equiv 1\pmod{q}\)

teljesül a kis Fermat tétel miatt. Ezért minden \(\displaystyle cq+1\le n\le cq+q-1\) esetén

\(\displaystyle np_1^{1!}p_2^{2!}\ldots p_n^{n!}\equiv nt\pmod{q}.\)

A \(\displaystyle (cq+1)t,(cq+2)t,\ldots,(cq+q-1)t\) számok közül semelyik kettő különbsége nem osztható \(\displaystyle q\)-val. Ez a \(\displaystyle q-1\) darab \(\displaystyle q\)-val nem osztható szám tehát \(\displaystyle q\)-val osztva mind különböző maradékot ad. Ennél fogva valamelyikük, mondjuk \(\displaystyle nt\), éppen \(\displaystyle q-1\) maradékot kell, hogy adjon. Ekkor viszont

\(\displaystyle s=np_1^{1!}p_2^{2!}\ldots p_n^{n!}+1\equiv nt+1\equiv 0\pmod{q},\)

vagyis \(\displaystyle p_{n+1}=q\), hiszen az \(\displaystyle s\) szám osztható \(\displaystyle q\)-val, a \(\displaystyle q\)-nál kisebb prímekkel osztva viszont 1 maradékot ad. Ez az ellentmondás igazolja a feladat állítását.


Statisztika:

23 dolgozat érkezett.
5 pontot kapott:Ágoston Tamás, Cséke Balázs, Éles András, Énekes Péter, Janzer Olivér, Karkus Zsuzsa, Karl Erik Holter, Kiss 902 Melinda Flóra, Márkus Bence, Mester Márton, Mészáros András, Réti Dávid, Somogyi Ákos, Strenner Péter, Weisz Ágoston, Zsakó András.
4 pontot kapott:Dudás 002 Zsolt, Nagy Róbert, Perjési Gábor, Popper Dávid, Weisz Gellért.
3 pontot kapott:1 versenyző.
2 pontot kapott:1 versenyző.

A KöMaL 2010. januári matematika feladatai