Bizonyítsuk be a következő oszthatóságot, n természetes szám (n! ) ^ (n+1) osztója-e (n^2)!?

n! = n * (n-1)!

Megállapodás kérdése, hogy n = 0 természetes szám-e, ami esetén: 1 | 0 értelmetlen.

Minden más esetben

(n * (n-1)!)^(legalább másodikon)

Tehát n^2 osztója a tagnak.

Ez elég nehéz feladat. Előtte egy segédfeladatot mutatok meg, aztán térek vissza erre.

A segédfeladat: Bizonyítsuk be, hogy n! osztója a (k*n+1)*(k*n+2)*...*(k*n+n) szorzatnak! (k természetes szám)

Bizonyítás:

n! = 1*2*...*n

Legyen 'i' egy 1 és n közé eső szám (ami persze így az egyik szorzótényezője n! -nak.) Lássuk be, hogy i osztója a (k*n+1)*(k*n+2)*...*(k*n+n) szorzatnak!

Legyen (k*n+1) i-vel való osztási maradéka r. Ha r =0, akkor nyilvánvalóan i osztója (k*n + 1)-nek, és így a szorzatnak is. Ha r > 0, akkor (k*n + 2) i-vel való osztási maradéka r+1, (k*n + 3) -é r+2, stb.. Mivel r<i (a maradéknak kisebbnek kell lennie az osztónál), és i<=n, a (k*n+1)*(k*n+2)*...*(k*n+n) szorzatban, ami n db tényezőből áll, nyilvánvalóan van olyan tényező, amelynek a fenti növekedéssel i, azaz 0 lesz az i-vel való osztási maradéka, tehát i-vel osztható lesz.

Tehát a (k*n+1)*(k*n+2)*...*(k*n+n) szorzat i-vel osztható. Mivel 1 <= i <= n, ez valamennyi i-re igaz, ezért a (k*n+1)*(k*n+2)*...*(k*n+n) szorzat n!-sal is osztható!

Az eredeti feladat bizonyítása:

n!^(n+1) = n!*n!*...*n! (Ezen n!-okból n+1 db van)

(n^2)! = n! * [(n+1)*(n+2)*...*(2n)] *[(2n+1)*(2n+2)*...*(3n)]*....*[((n-1)*n + 1)*((n-1)*n + 2)*...*(n*n)]

(Itt a szögletes zárójelekkel csak az egyes összefüggő szorzatokat akartam szemléltetni.) Egy ilyen szorzat (k*n+1)*(k*n+2)*...*(k*n+n) alakú, ahol 1 <= k < n. Mint a segédfeladatban láttuk, n! osztója egy ilyen szorzatnak.

n! * [(n+1)*(n+2)*...*(2n)] * [(2n+1)*(2n+2)*...*(3n)]*....*[((n-1)*n + 1)*((n-1)*n + 2)*...*(n*n)] első tényezője n!, ami persze n!-sal osztható. Az első szögletes zárójelben lévő szorzat, (n+1)*(n+2)*...*(2n) is osztható a fentiek alapján n!-sal, a következő szögletesben lévő is, és így tovább az utolsóig.

Igen ám, de így csak azt sikerült bebizonyítani, hogy az (n^2)! = n! * [(n+1)*(n+2)*...*(2n)] * [(2n+1)*(2n+2)*...*(3n)]*....*[((n-1)*n + 1)*((n-1)*n + 2)*...*(n*n)] szorzat n!^n -nel osztható. Miért osztható n!^(n+1)-el is, azaz hol lehet benne még egy n!-t találni?

Az első szögletes zárójelben lévő szorzat, (n+1)*(n+2)*...*(2n) utolsó tényezője 2n, ami 2-vel osztható. A második szögletes zárójelben lévő szorzat, (2n+1)*(2n+2)*...*(3n) utolsó tényezője 3n, ami 3-mal osztható. És így tovább az utolsó szögletes zárójelben lévő szorzatig, aminek utolsó tényezője n*n, tehát n-nel osztható.

n! = 2*3*...*n, tehát a szögletes zárójelekben lévő szorzatokból "összejött" még egy n!. Ezzel (végre) kész a bizonyítás!