Feladat: 1999. évi Nemzetközi Matematika Diákolimpia 21. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Zábrádi Gergely 
Füzet: 1999/október, 390 - 392. oldal  PDF  |  MathML 
Témakör(ök): Oszthatósági feladatok, Euler-Fermat-tételek, Binomiális tétel, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 1999/szeptember: 1999. évi Nemzetközi Matematika Diákolimpia 21. feladata

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.

Föltehető, hogy n>1, hiszen n=1 tetszőleges p prímmel megoldás. Legyen q az n legkisebb prímosztója, azaz n=qα⋅m, ahol q∤m. q választásából látszik, hogy (q,m)=1, és az is, hogy az m páratlan. Ekkor q∣n∣(p-1)n+1, azaz
(p-1)qα⋅m≡-1(modq).
A kis Fermat-tétel szerint (p-1)q≡p-1(modq). Ennek ismételt alkalmazásával
(p-1)n≡(p-1)m(modq),és így(p-1)m≡-1(modq).(1)
Ebből az is következik, hogy (q,p-1)=1, tehát ismét felhasználva a kis Fermat-tételt
(p-1)q-1≡1(modq).(2)
(1)-et négyzetre emelve
(p-1)2m≡1(modq)(3)
Ha d jelöli q-1 és 2m legnagyobb közös osztóját, akkor az euklideszi algoritmus felhasználásával (2)-ből és (3)-ból (p-1)d≡1(modq) következik.
A d meghatározásához vegyük észre, hogy q választása szerint az m minden prímosztója nagyobb q-nál, így (q-1)-nek és m-nek nincs közös prímosztója. Így d=(q-1,2m) vagy 1, vagy pedig 2. Így mindenképpen (p-1)2≡1(modq).
Ez pontosan akkor teljesül, ha p-1≡1(modq), vagy pedig p-1≡-1(modq).
Az első esetben (1)-ből (p-1)m≡1≡-1(modq), azaz q=2 és így p≡2(modq) miatt p=2. Ekkor a feltételből n=2 következik, és így a p=2, n=2 megoldást kapjuk.
A második esetben p-1≡-1(modq), azaz q∣p, és így q=p>2, n=pα⋅m, a feltételből pedig
pα(p-1)∣(p-1)n+1(4)
következik.
Megmutatjuk, hogy p kitevője (p-1)n+1 prímtényezős felbontásában pontosan α+1. Ebből aztán (4) szerint α(p-1)≤α+1, azaz α⋅(p-2)≤1, tehát α=1 és p=3 adódik.
1+(p-1)n a binomiális tétel szerint (az n páratlan):
1+∑k=0n(-1)n-k(nk)pk=1-1︸0+(n1)p+∑k=2n(-1)n-k⋅(nk)⋅pk.
Az összeg első tagja (n1)p=pα+1⋅m, és tudjuk, hogy p∤m. Azt állítjuk, hogy a további tagok valamennyien oszthatók pα+2-vel, és így 1+(p-1)n=pα+1(m+p⋅K) alakú, és így a második tényező valóban nem osztható p-vel.
Legyen tehát k≥2, és tekintsük a k-adik tagot (n=pα⋅m):
(nk)pk=nk(n-1k-1)⋅pk=pα+k⋅mk(n-1k-1).
Ha p≥3 és k≥2, akkor pk-1>k (ez k-ra vonatkozó indukcióval nyilvánvaló), és így a p prímszám kitevője a k nevezőben legfeljebb k-2. Mivel a pα+k⋅m⋅(n-1k-1) szorzatban csak a k-val való osztás csökkentheti a p kitevőjét, azért ez a kitevő valóban legalább α+k-(k-2)=α+2.
A második esetben tehát arra jutottunk, hogy a p prímszám csak 3 lehet, a feltétel pedig így
n2∣2n+1.

Ismeretes, hogy ez csak az n=1 és n=3 esetben teljesül. Ez volt az 1990. évi pekingi Matematikai Diákolimpia 3. feladata. Megoldása megtalálható Reiman István: Nemzetközi Matematikai Diákolimpiák 1959‐1994 (Typotex Kiadó, Budapest, 1997) című könyvének 442‐444. oldalán.
 
Megjegyzés. Az n≤2p feltétel felhasználásával természetesen nincs szükség erre a hivatkozásra.

  Zábrádi Gergely megoldása