Feladat: F.2193 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Angyal T. ,  Arató M. ,  Bakó I. ,  Beleznay F. ,  Bohus G. ,  Buczolich Z. ,  Bukta Gy. ,  Bölcsföldi L. ,  Cseri I. ,  Csordás A. ,  Erdélyi Tamás ,  Feledi Gy. ,  Fordán T. ,  Gabriel Z. ,  Grolmusz V. ,  Hajnal P. ,  János Ágnes ,  Kiss 352 Gy. ,  Kovács 134 I. ,  Mala J. ,  Mészáros a. ,  Nagy 647 G. ,  Náray Zsófia ,  Pátkai A. ,  Pintér F. ,  Ruisz T. ,  Schwarcz P. ,  Sz. Nagy Cs. ,  Szalai Cs. ,  Szegedy P. ,  Szeles J. ,  Takács 405 Gabriella ,  Tálas Cs. ,  Tóth 396 J. ,  Varga J. ,  Varga Lívia ,  Varga T. ,  Winkler R. ,  Öreg E. Zs. 
Füzet: 1979/november, 124. oldal  PDF file
Témakör(ök): Binomiális együtthatók, Hatványösszeg, Maradékos osztás, Feladat
Hivatkozás(ok):Feladatok: 1979/március: F.2193

Bizonyítsuk be, hogy a következő szám osztható 1979-cel:
i=11978i1976.(1)

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.

Azt állítjuk, hogy i=11978in minden 1978-nál kisebb pozitív egész n esetén osztható 1979-cel. Ezt n-re vonatkozó teljes indukcióval bizonyítjuk.
n=1 esetén igaz az állítás, mivel i=11978i=1979989.
A következőkben belátjuk, hogy ha i=11978ik osztható 1979-cel minden n-nél kisebb k természetes szám esetén (n<1978), akkor osztható k=n esetén is.
A binomiális tétel szerint

2n+1=(1+1)n+1=1n+1+(n+11)1n+(n+12)1n-1+...+(n+1n)1+13n+1=(2+1)n+1=2n+1+(n+11)2n+(n+12)2n-1+...+(n+1n)2+11979n+1=(1978+1)n+1=1978n+1+(n+11)1978n+(n+12)1978n-1+...++(n+1n)1978-1.
Összeadva ezeket az egyenlőségeket:
1979n+1=1+(n+11)i=11978in+(n+12)i=11978in-1+...+(n+1n)i=11978i+1978.
Innen
(n+1)i=11978in=1979n+1-1979-(n+12)i=11978in-1-...-(n+1n)i=11978i.
Az indukciós feltevést figyelembe véve a jobb oldal minden tagja osztható 1979-cel, ezért (n+1)i=11978in is osztható vele.
Mivel 1979 prímszám és n+1<1979, ez csak úgy lehetséges, ha i=11979in osztható 1979-cel. Állításunkat ezzel bebizonyítottuk. Ebből n=1976 esetén a feladat állítását kapjuk.
 

 Erdélyi Tamás (Budapest, Berzsenyi D. Gimn., IV. o. t.)
 
Megjegyzés. Hasonló módon igazolható, hogy ha p prímszám, k<p pozitív egész, akkor i=1p-1ik osztható p-vel.