Feladat: 2000. évi Nemzetközi Matematika Diákolimpia 22. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Zábrádi Gergely 
Füzet: 2000/október, 390 - 391. oldal  PDF file
Témakör(ök): Euler-Fermat-tételek, Euklideszi algoritmus, Maradékos osztás, kongruenciák, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 2000/szeptember: 2000. évi Nemzetközi Matematika Diákolimpia 22. feladata

Döntsük el, hogy létezik-e olyan n pozitív egész szám, amelyre teljesül, hogy n pontosan 2000 különböző prímszámmal osztható, és 2n+1 osztható n-nel.

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.

Belátjuk, hogy minden pozitív egész k-hoz található olyan pozitív egész n úgy, hogy (2n+1) osztható n-nel, és n-nek pontosan k darab prímosztója van. 
(Így k=2000-re is létezik ilyen n.)
k szerinti teljes indukcióval bizonyítjuk az állítást. k=1-re igaz: 929+1.
k=2-re: 9192919+1.
Tegyük fel, hogy k-ra igaz (k2):

p12p2p3...pk2p12p2p3...pk+1,p1=3<p2=19<p3<...<pk.

Segédtétel. Ha p>3 prím, akkor (2p+1)-nek van p-nél nagyobb prímosztója.
Bizonyítás. Legyen a q a (2p+1)-nek egy p-nél nem nagyobb prímosztója. Ekkor q>2 és
2p-1(modq).Négyzetre emelve22p1(modq).
A kis Fermat-tétel szerint 2q-11(modq). Innen az euklideszi algoritmus alkalmazásával kapjuk, hogy 2(2p,q-1)1(modq). pq-1, mert q-1<p, így (2p,q-1)=2
22=41(modq),tehátq=3.

Másrészt 92p+1, mert egyébként 22p1(mod9) és 261(mod9) miatt 2(6,2p)1(mod9) az euklideszi algoritmus miatt, ami 221(mod9), és ez ellentmondás.
Ha tehát (2p+1)-nek nincs p-nél nagyobb prímosztója, akkor 2p+13, ami ellentmondás. Ezzel a segédtételt beláttuk.
Legyen ezután pk+1 a segédtétel szerinti prím, tehát pk+1>pk, és pk+12pk+1.
2pk-1(modpk+1),és így2p12p2p3...pkpk+1(-1)p12p2p3...pk-1pk+1=-1(modpk+1),azazpk+12p12p2p3...pkpk+1+1.
Másrészt az indukciós feltevés miatt p12p2...pk2p12p2...pk+1, tehát
2p12p2...pk-1(modp12p2...pk).2p12p2...pkpk+1(-1)pk+1=-1(modp12p2...pk).p12p2...pkpk+12p12p2...pkpk+1+1,
mert p12p2...pk és pk+1 relatív prímek. Így k+1-re n=p12p2...pkpk+1 megfelelő, amivel az indukciós bizonyítást befejeztük.
 Zábrádi Gergely (Győr, Révai M. Gimn., 12. o.t.)