Feladat:	B.4397	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Barna István ,  Le Vivien ,  Strenner Péter
Füzet:	2013/március, 155 - 156. oldal		PDF  |  MathML
Témakör(ök):	Algebrai átalakítások, Legnagyobb közös osztó, Összefüggések binomiális együtthatókra, Feladat
Hivatkozás(ok):	Feladatok: 2011/november: B.4397

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. Azt fogjuk igazolni, hogy az $n$ prímtényezős alakjában lévő bármelyik $p^a$ prímhatvány osztója az $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\cdot \left(n\mathrm{,}k\right)$ számnak. Legyen a $k$ prímtényezős alakjában a $p$ prímszám kitevője $b$. Ha $a\le b$, akkor $p^a\mid \left(n\mathrm{,}k\right)$, így $\begin{array}{c}{\displaystyle p^a|\left(\genfrac{}{}{0ex}{}{n}{k}\right)\cdot \left(n\mathrm{,}k\right)\mathrm{.}}\end{array}$ Ha $a>b$, akkor végezzük el a következő átalakítást: $\begin{array}{c}{\displaystyle \left(\genfrac{}{}{0ex}{}{n}{k}\right)\cdot \left(n\mathrm{,}k\right)=\frac{n!}{k!\left(n-k\right)!}\cdot \left(n\mathrm{,}k\right)=\frac{n}{k}\cdot \frac{\left(n-1\right)!}{\left(k-1\right)!\left(n-k\right)!}\cdot \left(n\mathrm{,}k\right)=n\cdot \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)\frac{\left(n\mathrm{,}k\right)}{k}\mathrm{.}}\end{array}$ Mivel $p^a\mid n$ és $p^b\mid \left(n\mathrm{,}k\right)$, azért $\begin{array}{c}{\displaystyle p^a|n\cdot \frac{\left(n\mathrm{,}k\right)}{k}\mathrm{,}\text{vagyis}{p}^a|n\cdot \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)\frac{\left(n\mathrm{,}k\right)}{k}\mathrm{.}}\end{array}$ Tehát ebben az esetben is igaz, hogy $p^a|\left(\genfrac{}{}{0ex}{}{n}{k}\right)\cdot \left(n\mathrm{,}k\right)$. Ezzel az állítást beláttuk.     2. megoldás. Szalay Mihály: Számelmélet című könyvének 1.13. tételére hivatkozunk. Ha $d=\left(n\mathrm{,}k\right)$, akkor léteznek $p$, $q$ egész számok, hogy $d=n\cdot p+k\cdot q$. Ekkor ${\displaystyle \begin{array}{cc}\hfill {\displaystyle \left(\genfrac{}{}{0ex}{}{n}{k}\right)\cdot \left(n\mathrm{,}k\right)}& {\displaystyle =\frac{n!}{k!\left(n-k\right)!}\cdot d=\frac{n!}{k!\left(n-k\right)!}\left(n\cdot p+k\cdot q\right)=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =\frac{n\cdot p\cdot n!}{k!\left(n-k\right)!}+\frac{k\cdot q\cdot n!}{k!\left(n-k\right)!}=n\cdot p\cdot \left(\genfrac{}{}{0ex}{}{n}{k}\right)+\frac{k\cdot q\cdot n\cdot \left(n-1\right)!}{k\cdot \left(k-1\right)!\left(n-k\right)!}=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =n\cdot \left(p\cdot \left(\genfrac{}{}{0ex}{}{n}{k}\right)+q\cdot \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)\right)\mathrm{.}}\hfill \end{array}}$ A zárójelben lévő szám egész szám, tehát $n|\left(\genfrac{}{}{0ex}{}{n}{k}\right)\cdot \left(n\mathrm{,}k\right)$.