Feladat: B.4241 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Ágoston Tamás ,  Cséke Balázs ,  Éles András ,  Énekes Péter ,  Janzer Olivér ,  Karkus Zsuzsa ,  Karl Erik Holter ,  Kiss 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 
Füzet: 2011/január, 16 - 17. oldal  PDF file
Témakör(ök): Feladat, Rekurzív sorozatok, Indirekt bizonyítási mód, Maradékos osztás, kongruenciák
Hivatkozás(ok):Feladatok: 2010/január: B.4241

Legyen p1=2, és n1 esetén jelölje pn+1 a np11!p22!...pnn!+1 szám legkisebb prímosztóját. Igazoljuk, hogy a p1,p2,... sorozatban minden prímszám előfordul.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. Legyen An+1=np11!p22!...pnn!+1. Először megmutatjuk, hogy minden prím legfeljebb egyszer szerepelhet a sorozatban. Ha ugyanis lenne két index, i<j, amelyekre pi=pj, akkor (j-1)p11!p22!...pj-1(j-1)! osztható pj-vel, mert tényezői között szerepel a pi, így ha hozzáadunk 1-et, akkor nem lesz osztható vele; ez viszont ellentmond pj definíciójának.
Tegyük föl, hogy van olyan p prím, amely nem szerepel a sorozatban. Belátjuk, hogy ekkor az An sorozat végtelen sok tagja osztható p-vel. Ez adja majd az ellentmondást, hiszen ha tekintjük a p-vel osztható An számokat, illetve azok legkisebb prímosztóját, akkor ezek nyilván nem nagyobbak p-nél, ugyanakkor mind különbözőek a fenti észrevételünk szerint, ami lehetetlen. Tehát elegendő belátnunk, hogy ha a p prím nem szerepel a sorozatban, akkor az An sorozat végtelen sok tagja osztható p-vel.
Legyen L=p11!p22!...pp-2(p-2)!; ez nyilván nem osztható p-vel, mert egyik tényezője sem osztható p-vel (és p prím).
Legyen n>p-1, ekkor An+1=nLpp-1p-1!ppp!...pnn!+1. Itt a pkk! (k>p-2) alakú tényezők p-vel való maradéka mindig 1 a kis Fermat-tétel szerint, hiszen pk nem osztható p-vel, illetve k! osztható (p-1)-gyel, mert az az egyik szorzó tényezője (pkk!pk(p-1)b(pkp-1)b1b(modp)).
Így An+1(nL+1)modp, ha n>p-1. Ezért, ha nL(-1)modp-nek létezik n-re nézve megoldása, akkor készen vagyunk, mert ha n0 egy ilyen megoldás, akkor az Atp+n0+1 számok mindegyikére

Atp+n0+1(tp+n0)L+1n0L+10(modp)
‐ legalábbis, ha t elég nagy ahhoz, hogy tp+n0 nagyobb legyen (p-1)-nél; ez biztosítja, hogy az An sorozat végtelen sok tagja osztható p-vel.
Végül az nL(-1)modp kongruenciának azért van megoldása, mert p prím, L pedig nem osztható p-vel, így L és p relatív prímek; emiatt a 0, L, 2L, 3L, ..., (p-1)L számok mind különböző maradékot adnak p-vel osztva, tehát e p darab szám valamelyikének a maradéka -1.