Feladat:	B.4634	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Andó Angelika ,  Baran Zsuzsanna ,  Di Giovanni Márk ,  Forrás Bence ,  Gyulai-Nagy Szuzina ,  Kúsz Ágnes ,  Lajkó Kálmán ,  Maga Balázs ,  Porupsánszki István ,  Schwarz Tamás ,  Szőke Tamás ,  Tóth Viktor ,  Williams Kada
Füzet:	2015/március, 152. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Prímtényezős felbontás, Binomiális együtthatók
Hivatkozás(ok):	Feladatok: 2014/május: B.4634

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.   Megoldás. A Legendre-formula szerint $m!$ prímtényezős felbontásában a $p$ prímszám kitevője $\begin{array}{c}{\displaystyle \sum _{i=1}^M\left[\frac{m}{p^i}\right]\mathrm{,}}\end{array}$ ahol $M$ a legnagyobb olyan egész, amelyre $p^M\le m$. Ebből következik, hogy $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ prímtényezős felbontásában a $p$ prímszám kitevője $\begin{array}{c}{\displaystyle \sum _{i=1}^N\left(\left[\frac{n}{p^i}\right]-\left[\frac{k}{p^i}\right]-\left[\frac{n-k}{p^i}\right]\right)\mathrm{,}}\end{array}$ ahol $N$ a legnagyobb olyan egész szám, amelyre még $p^N\le n$. Mivel minden $x$, $y$ valós számra fennáll az $\left[x+y\right]-\left[x\right]-\left[y\right]\le 1$ egyenlőtlenség, ebben az összegben minden tag értéke legfeljebb 1, vagyis $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ prímtényezős felbontásában $p$ kitevője legfeljebb $N$. Mivel $p^N\le n$, az $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ minden prímhatvány osztója legfeljebb $n$. Így $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ csak akkor lehet prímhatvány, ha $k=1$ vagy $k=n-1$, és $\left(\genfrac{}{}{0ex}{}{n}{1}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-1}\right)=n$ prímhatvány, hiszen $1<k<n-1$ esetén $\left(\genfrac{}{}{0ex}{}{n}{k}\right)>n$, ha pedig $k=n$, akkor $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=1$. Ezzel bebizonyítottuk, hogy $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ pontosan akkor prímhatvány, ha $n$ prímhatvány és $k=1$ vagy $k=n-1$.   Megjegyzések. 1. Sylvester és Schur egy nevezetes tétele szerint, ha $2k\le n$, akkor az $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ binomiális együtthatónak van $k$-nál nagyobb prímosztója. Ha $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=p^{\alpha }$ prímhatvány, akkor ez a prímosztó csak $p$ lehet, és mivel a $n\left(n-1\right)\text{...}\left(n-k+1\right)$ szorzatnak pontosan egy tagját osztja, ezért $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=p^{\alpha }\le n$ azonnal adódik. 2. A feladat egy lehetséges általánosítása, ha azt vizsgáljuk, hogy az $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ binomiális együttható mikor lehet teljes hatvány. Erről a problémáról Győry Kálmán: Binomiális együtthatók és teljes hatványok1 című cikkében olvashatunk, ami a KöMaL 1999/1. számában jelent meg. 1http://www.komal.hu/cikkek/gyory/binom/binom.h.shtml.