KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley