Feladat: B.4178 Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 2009/november, 479 - 480. oldal  PDF file
Témakör(ök): Feladat, Binomiális együtthatók, Legnagyobb közös osztó
Hivatkozás(ok):Feladatok: 2009/április: B.4178

Bizonyítsuk be, hogy tetszőleges n, k pozitív egészek esetén az (nk),(n+1k),...,(n+kk) számok legnagyobb közös osztója 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.

I. megoldás. Ha nk, akkor az adott számok között szerepel (kk)=1, ezért az állítás nyilvánvaló.
Tudjuk, hogy minden 0m egészre (m)+(m+1)=(m+1+1). Ezért

(m)=(m+1+1)-(m+1),
vagyis (m+1) és (m+1+1) minden közös osztója egyúttal (m)-nek is osztója.
Legyen az
(nk),(n+1k),...,(n+kk)
számok legnagyobb közös osztója d. Ekkor az előző bekezdésben leírtakat az +1=k és m=n,n+1,...,n+k-1 esetekben alkalmazva kapjuk, hogy d osztója az
(nk-1),(n+1k-1),...,(n+k-1k-1)
számok mindegyikének. Ismét alkalmazzuk az oszthatóságra vonatkozó állításunkat, most az +1=k-1 és m=n,n+1,...,n+k-2 számokra. Azt kapjuk, hogy d osztója az
(nk-2),(n+1k-2),...,(n+k-2k-2)
számoknak is. Ezt az eljárást lépésről-lépésre folytatva kapjuk, hogy d osztója az
(nk-i),(n+1k-i),...,(n+k-ik-i)
számoknak, minden i<k pozitív egész esetén.
Ezért, ha i=k-1, akkor azt kapjuk, hogy (n1) és (n+11) is, s így
(n+11)-(n1)=(n0)=1
is osztható d-vel. Vagyis d=1, ami éppen a bizonyítandó állítás.
 
II. megoldás. Ha nk, akkor az első megoldásban leírtak miatt igaz az állítás. A továbbiakban tegyük fel, hogy n>k. Ekkor azt kell megmutatnunk, hogy bármely p prímszámra található az (nk),(n+1k),...,(n+kk) számok között legalább egy olyan, amely nem osztható p-vel.
Rögzítsük a p prímszámot. Tekintsük az n-k+1, n-k+2, ..., n, n+1, ..., n+k számokat. Az adott binomiális együtthatók mindegyike egy olyan törtként írható fel, amelynek számlálójában ezek közül k darab egymást követő szám szorzata áll, nevezője pedig k!. Ha p nem osztója egyik számnak sem, akkor készen vagyunk. Ha p osztója az n-k+1, n-k+2, ..., n+k számok közül néhánynak, akkor pedig válasszunk ki közülük egy olyan m számot, amely p-nek a lehető legnagyobb hatványával, mondjuk pα-val osztható. Először vizsgáljuk meg az n-k+1mn esetet. Tekintsük az
(m+kk)=(m+k)(m+k-1)...(m+1)k(k-1)...1
binomiális együtthatót. Az α definíciójából következően a számlálóban egyik tényező sem osztható pα+1-nel. Ha pedig 0<βα tetszőleges pozitív egész, akkor m választása miatt minden i pozitív egész esetén m+i pontosan akkor osztható pβ-val, ha i osztható vele. Ezért a törtet egyszerűsíthetjük pβ-val. Minden lehetséges β értékre elvégezve az egyszerűsítést, olyan törtet kapunk, amelynek sem a számlálója, sem a nevezője nem osztható p-vel. Tehát ebben az esetben van a feladatban szereplő binomiális együtthatók közt olyan, amelyik nem osztható p-vel.
Az n<mn+k esetben pedig az
(m-1k)=(m-k)(m-k+1)...(m-1)k(k-1)...1
binomiális együtthatót érdemes tekinteni. Ekkor minden 1ik esetén a tört számlálójában szereplő m-i tényezőről állítható, hogy p-nek pontosan akkora hatványával osztható, mint a tört nevezőjében szereplő i tényező. Tehát az egyszerűsítések elvégzése után látható, hogy (m-1k) nem osztható p-vel.
Ezzel a feladat állítását beláttuk.