Feladat:	F.3288	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	2000/május, 289. oldal		PDF  |  MathML
Témakör(ök):	Teljes indukció módszere, Oszthatóság, Feladat
Hivatkozás(ok):	Feladatok: 1999/május: F.3288

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.     Megjegyzés az F. 3288. feladathoz       F. 3288. Legyenek $n$ és $k$ pozitív egészek és $p$ prímszám úgy, hogy $p^k|n!$. Bizonyítsuk be, hogy ekkor $n!$ osztható ${\left(p!\right)}^k$-nal is. A KöMaL 2000/1. számának 36‐37. oldalán a fenti feladatra két megoldást is közöltünk. Amint arra Kiss Gergely (Fazekas M. Főv. Gyak. Gimn., 12. o.t.) felhívta a figyelmünket, az I. megoldás hibás, az állítás, amelyből az indukció kiindul, nem igaz. Abból ugyanis, hogy $m$ a legkisebb olyan egész szám, amire $p^{\ell }\mid m!$, nem következik, hogy $m+p$ a legkisebb olyan pozitív egész, amelynek faktoriálisa $p^{\ell +1}$-nel osztható. A legegyszerűbb ellenpélda a $p=\ell =2$. Ekkor az a legkisebb $m$, amire $m!$ osztható $4$-gyel, az $m=4$; és $4!$ osztható $2^3$-nel is.   A megjelent hibás teljes indukciós bizonyítás helyett Fried Ervin az alábbi bizonyítást bocsátotta a lap rendelkezésére:   Legyen $p$ rögzített prímszám, és jelölje $k\left(n\right)$ azt a legnagyobb kitevőt, amelyre $p^{k\left(n\right)}$ osztója $n!$-nak. Elég az állítást $k\left(n\right)$-re bizonyítani, hiszen $k<k\left(n\right)$ esetén ${\left(p!\right)}^k$ osztója ${\left(p!\right)}^{k\left(n\right)}$-nek. (Az eddigiek csak az egyszerűbb számolást szolgálják.) Azt kell tehát bizonyítani, hogy ${\left(p!\right)}^{k\left(n\right)}$ osztója $n!$-nak. Ezt az állítást $n$-re vonatkozó teljes indukcióval bizonyítjuk. Az $n=1$ esetben $k\left(1\right)=0$ következtében az állítás igaz. Tegyük fel, hogy az állítás teljesül minden $n$-nél kisebb természetes szám esetében, és vizsgáljuk $n!$-t. Ha $p$ nem osztója $n$-nek, akkor $k\left(n-1\right)=k\left(n\right)$ miatt ${\left(p!\right)}^{k\left(n\right)}$ osztója $\left(n-1\right)!$-nak; így $n!$-nak is. Legyen most $n=pm$. Mivel $p$ prímszám, azért az $n!$-ban fellépő maximális $p$-hatvány megegyezik az $1\cdot p$, $2\cdot p$, $\text{...}$, $m\cdot p$ számok szorzatában fellépő maximális prímhatvánnyal. Ez a szorzat pontosan $p^m\cdot m!$. Így $k\left(pm\right)=m+k\left(m\right)$. Bontsuk fel most az $n!$-t $m+1$ tényező szorzatára. Az első $m$ tényező a következő: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle 1\cdot 2\cdots \left(p-1\right)\mathrm{,}}\\ \hfill {\displaystyle ⋮}\\ \hfill {\displaystyle \left(ip+1\right)\cdot \left(ip+2\right)\cdots \left(\left(i+1\right)p-1\right)\mathrm{,}}\\ \hfill {\displaystyle ⋮}\\ \hfill {\displaystyle \left(\left(m-1\right)p+1\right)\cdot \left(\left(m-1\right)p+2\right)\cdots \left(mp-1\right)\mathrm{.}}\end{array}}}\end{array}$ Ezen tényezők mindegyike osztható $\left(p-1\right)$ faktoriálissal, hiszen bármilyen $t$ egész szám esetén $t$ egymás utáni egész szám szorzata osztható $t!$-sal. Ez a szorzat tehát osztható a $\left(p-1\right){!}^m$ számmal. A fennmaradó tényező a $p^m\cdot m!$ szorzat. A $p^m$ tényezőt az előző szorzathoz hozzávéve egy olyan szorzatot kapunk, amely osztható ${\left(p!\right)}^m$-nel. Az indukciós feltevés és $m<n$ miatt $m!$ osztható ${\left(p!\right)}^{k\left(m\right)}$-nel. A már belátott $k\left(n\right)=m+k\left(m\right)$ összefüggésből következik az állítás.