Feladat: N.136 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bérczi Gergely ,  Braun Gábor ,  Frenkel Péter ,  Lippner Gábor ,  Lukács László ,  Pap Gyula 
Füzet: 1997/december, 550 - 551. oldal  PDF  |  MathML 
Témakör(ök): Összefüggések binomiális együtthatókra, Oszthatósági feladatok, Indirekt bizonyítási mód, Nehéz feladat
Hivatkozás(ok):Feladatok: 1997/április: N.136

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 továbbiakban xmody jelöli x osztási maradékát y-nal osztva.
A megoldáshoz két ismert lemmát használunk fel:
*a)Tetszőleges n, k pozitív egészekre és p prímszámra (nk) akkor és csak akkor osztható p-vel, ha valamilyen pozitív egész α-ra nmodpα<kmodpα.
*b)Ha p prím és pα∣(nk), akkor pα≤n.
Mivel az amodp>bmodp állítás ekvivalens azzal, hogy (b-a)modp>bmodp, elég az a≤b2 esetre megoldani a feladatot.
Az a) lemma szerint, ha egy p prímszám osztója (ba)-nak, akkor valamilyen α ra bmodpα<amodpα. Ha p>a, akkor α=1 esetén is teljesül a feltétel, mert
amodp=a=amodpα>bmodpα≥bmodp.
Ha pedig p>b, akkor csak α=1 lehetséges. A feladat állításához ezért elég a következőt igazolni:
A (ba) számnak létezik olyan p prímosztója, amelyre p>min(a,[b]).
Legyen a0=min(a,[b]). Ha a0=1, akkor az állítás triviális. Feltehetjük tehát, hogy a0≥2. Legyenek az a0-nál nem nagyobb prímek p1, ..., ps, ezek kitevője (ba)-ban α1, ..., αs. A b) lemma szerint piαi≤b, és ha (ba)-nak nincs más prímosztója, akkor
(ba0)≤(ba)=p1α1⋅...⋅psαs≤bs.(1)
Másrészt
(ba0)=ba0⋅b-1a0-1⋅...⋅b-a0+11>(ba0)a0≥ba02,
következésképp s>a02. Mivel s az a0-nál nem nagyobb prímszámok száma, ez azt jelenti, hogy a0=3, a0=5 vagy a0=7.
Ha a0=3, akkor s=2, és (1) alapján (b3)≤b2, vagyis b≤8; ha a0=5, akkor s=3, (1) alapján (b5)≤b3, azaz b≤15; ha pedig a0=7, akkor s=4, (b7)≤b4, azaz b≤23. Mindhárom eset ellentmond az a0≤b feltételnek.
 
Megjegyzések. 1. A két idézett lemma az úgynevezett Legendre-formula segítségével bizonyítható be. Eszerint a p prímszám kitevője n! prímtényezős felbontásában
[np]+[np2]+[np3]+...,
ennek következménye, hogy az (nk) binomiális együtthatóban p kitevője
∑ν=1∞([npν]-[kpν]-[n-kpν]).
Ebben az összegben minden egyes tag 0 vagy 1; a ν-edik tag akkor és csak akkor 1, ha nmodpν<kmodpν. Ebből az a) és a b) állitás is következik.
2. Több versenyző hivatkozott a Sylvester‐Schur-tételre, ami azt állítja, hogy k≤n2 esetén (nk)-nak létezik k-nál nagyobb prímosztója. (A tétel, bizonyítás nélkül, megtalálható pl. Erdős‐Surányi: Válogatott fejezetek a számelméletből c. könyvének 195. oldalán.) A megoldás módszerével a Sylvester‐Schur-tételnek egy valamivel gyengébb változata könnyen igazolható: Létezik olyan pozitív c konstans, amelyre tetszőleges k≤cn esetén (nk)-nak van k-nál nagyobb prímosztója.