Feladat: N.137 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Frenkel Péter ,  Gerbicz Róbert ,  Lukács László ,  Pap Gyula 
Füzet: 1998/január, 33 - 34. oldal  PDF file
Témakör(ök): Konstruktív megoldási módszer, Legkisebb közös többszörös, Oszthatósági feladatok, Ellenpélda, mint megoldási módszer a matematikában, Nehéz feladat
Hivatkozás(ok):Feladatok: 1997/április: N.137

a) Bizonyítsuk be, hogy tetszőleges k pozitív egészhez léteznek olyan a1<a2<...<ak pozitív egész számok, amelyekre  1i,jk,  ij esetén ai-ajai1997.
b) Bizonyítsuk be, hogy létezik olyan c>0 valós szám, hogy tetszőleges, a fenti feltételeket kielégítő a1, a2, ..., ak számokra ak>2ck.

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.

a) Legyen A az 1, 2, ..., k számok legkisebb közös többszöröse, és legyen ai=iA minden i-re. Ekkor ij esetén ai-aj=(i-j)AA2ai1997, tehát ez a konstrukció megfelelő.

b) Az állítás k=1 esetén az a1=1 ellenpélda miatt nem igaz, de k2 esetén igaz, ezt bizonyítjuk be. Legyen először k4, és tekintsünk egy tetszőleges, k2-nél nem nagyobb p prímet. Két különböző ai és aj nem adhatja ugyanazt a 0-tól különböző maradékot p-vel osztva, mert aiaj(modp) esetén pai-ajai1997. Ebből következik, hogy a p-vel nem osztható ai-k száma legfeljebb p-1, és a p-vel osztható ai-k száma legalább k-p+1[k+12].

Tekintsük a B=a1a2...ak szorzatot. Az előbbiek szerint ha p<k2 prím, akkor B osztható p[(k+1)2]-vel, ezért

ak>B1k(p<k2p[(k+1)2])1k(p<k2p)12.

De ismeretes (lásd megjegyzésünket), hogy létezik olyan pozitív c0 konstans, amelyre tetszőleges x2 esetén pxp>2c0x, ezért ak>214c0k.
Ha k=2 vagy k=3, akkor ak2>214k. A c számnak ezért választhatjuk 14c0 és 14 közül a kisebbet.
 
Megjegyzés. A prímszámtétel egyik formája azt mondja ki, hogy
limxpxlogpx=1,
vagy másképpen, tetszőleges ε>0-ra, ha x elég nagy,
e(1-ε)x<pxp<e(1+ε)x.

Ennél valamivel gyengébb alsó és felső becslést be lehet bizonyítani viszonylag egyszerű, elemi úton. Szalay Mihály: Számelmélet (Tankönyvkiadó, 1991.) c. könyvének 143‐146. oldalain megtalálható többek között annak bizonyítása, hogy n5 esetén
n<p2np>22n(2n)n4-2n3=2232n(2n)2n.
Ebből következik, hogy pxp>2(23-ε)x, ha x elég nagy.
Az idézett könyv 140. oldalán megtalálható 3.2. tétel szerint pxp<4x. Ebből nem nehéz bebizonyítani, hogy az első megoldásban szereplő A szám nem nagyobb, mint 4(1+ε)k, és így a b) állítás a konstanstól eltekintve éles.