Feladat:	F.3288	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Ábrány Miklós ,  Dancsó Zsuzsanna ,  Győri Nikolett ,  Harangi Viktor ,  Keszegh Balázs ,  Lábó Eszter ,  Lábó Melinda ,  Máthé András ,  Naszódi Gergely ,  Papp Dávid ,  Terpai Tamás ,  Vitéz Ildikó
Füzet:	2000/január, 36 - 37. 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.   I. megoldás. Az állítást $k$ szerinti indukcióval bizonyítjuk. A $k=1$ eset így szól: ha $p$ prím és $p\mid n!$, akkor $p!\mid n!$; ez igaz, hiszen $p$ prím lévén, $n\ge p$. Tegyük fel, hogy az állítás $k=\ell$-re igaz, és tételezzük fel, hogy $p^{\ell +1}\mid n!$. Jelölje $m$ a legkisebb olyan pozitív egészet, amelyre $p^{\ell }\mid m!$; ekkor $m+p$ a legkisebb olyan pozitív egész, amelynek faktoriálisa $p^{\ell +1}$-nel osztható, így $n\ge m+p$. Azonban $\left(m+p\right)!=m!\cdot \left(\genfrac{}{}{0ex}{}{m+p}{p}\right)p!$; itt $m!$ osztható $p^{\ell }$-nel, ezért az indukciós feltevés szerint ${\left(p!\right)}^{\ell }$-nel is osztható, tehát $m!p!$ osztható ${\left(p!\right)}^{\ell +1}$-nel. Mivel $\left(\genfrac{}{}{0ex}{}{m+p}{p}\right)$ egész, azért ebből ${\left(p!\right)}^{\ell +1}\mid \left(m+p\right)!\mid n!$, így az állítás $k=\left(\ell +1\right)$-re is igaz.  Papp Dávid (Budapest, Szent István Gimn., 11. o.t.)   II. megoldás. Felhasználjuk, hogy ha $q$ prím, akkor $n!$ a $q$-nak pontosan az $\left(\left[\frac{n}{q}\right]+\left[\frac{n}{q^2}\right]+\text{...}\right)$-adik hatványával osztható (vagyis $q$-nak az 1-gyel magasabb hatványa már nem osztója $n!$-nak). Tegyük fel ezután, hogy $p^k\mid n!$; $k$ értékét esetleg növelve feltehető, hogy $p^{k+1}$ már nem osztója $n!$-nak, azaz $\begin{array}{c}{\displaystyle k=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\text{...}}\end{array}$ (1) A ${\left(p!\right)}^k$ minden $p$-től különböző prímosztója $p$-nél kisebb, és egy ilyen $q$ prímnek pontosan a $k\left(\left[\frac{p}{q}\right]+\left[\frac{p}{q^2}\right]+\text{...}\right)$-adik hatványa osztója ${\left(p!\right)}^k$-nak. Mivel ${\left(p!\right)}^k$ a $p$-nek pontosan a $k$-adik hatványával osztható, azért elegendő belátni, hogy $\begin{array}{c}{\displaystyle k\left(\left[\frac{p}{q}\right]+\left[\frac{p}{q^2}\right]+\text{...}\right)\le \left[\frac{n}{q}\right]+\left[\frac{n}{q^2}\right]+\text{...}\mathrm{,}}\end{array}$ (2) azaz hogy $n!$ a $q$-nak legalább akkora hatványával osztható, mint ${\left(p!\right)}^k$. A (2) egyenlőtlenséget tagonként igazoljuk, megmutatva, hogy minden $a\ge 1$ egészre és $q<p$ prímre $\left[\frac{n}{q^a}\right]\ge k\cdot \left[\frac{p}{q^a}\right]$. Az (1) szerint $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle k\left[\frac{p}{q^a}\right]=\left(\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\text{...}\right)\left[\frac{p}{q^a}\right]\le \left[\frac{n}{p}+\frac{n}{p^2}+\text{...}\right]\left[\frac{p}{q^a}\right]=\left[\frac{n}{p-1}\right]\cdot \left[\frac{p}{q^a}\right]\mathrm{.}}\end{array}}}\end{array}$ Mivel $q^a$ és $p$ relatív prímek, azért $\left[\frac{p}{q^a}\right]=\left[\frac{p-1}{q^a}\right]$, így $\begin{array}{c}{\displaystyle \left[\frac{n}{p-1}\right]\left[\frac{p}{q^a}\right]=\left[\frac{n}{p-1}\right]\cdot \left[\frac{p-1}{q^a}\right]\le \left[\frac{n}{p-1}\cdot \frac{p-1}{q^a}\right]=\left[\frac{n}{q^a}\right]\mathrm{,}}\end{array}$ amit bizonyítani kellett.  Terpai Tamás (Fazekas M. Főv. Gyak. Gimn., 12. o.t.)