Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem B. 4241. (January 2010)

B. 4241. Let p1=2, and for n\ge1 let pn+1 denote the smallest prime factor of the number np_1^{1!}p_2^{2!}\ldots p_n^{n!}+1. Prove that every prime number occurs in the sequence p_1,p_2,\dots\,.

(5 pont)

Deadline expired on February 10, 2010.


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

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.


Statistics:

23 students sent a solution.
5 points:Á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 points:Dudás 002 Zsolt, Nagy Róbert, Perjési Gábor, Popper Dávid, Weisz Gellért.
3 points:1 student.
2 points:1 student.

Problems in Mathematics of KöMaL, January 2010