Podzielność przez liczbę pierwszą

[tomwanderer]

Mam takie zadanie, raczej jedno z prostszych, ale niestety jakoś nigdy nie przepadałem za wykazywaniem podzielności ani za liczbami pierwszymi.

Wykazać, że jeżeli \(\displaystyle{ n}\) jest potęgą liczby pierwszej \(\displaystyle{ p}\), to \(\displaystyle{ {n \choose k}}\) jest podzielne przez \(\displaystyle{ p}\), o ile \(\displaystyle{ 1\le k \le n-1}\).

Nieco się nad tym zastanawiałem i ostatecznie doszedłem do wniosku, że uzasadnienie musi być dość proste. Proszę o weryfikację:

Rozpiszmy:

\(\displaystyle{ {p^m \choose k}=\frac{(p^m)!}{k!(p^m-k)!}=\frac{(p^m-k+1)(p^m-k+2)\cdot...\cdot p^m}{1\cdot 2\cdot...\cdot k}}\)

Czy wystarczy stwierdzić, że:

1. W liczniku oraz w mianowniku mamy \(\displaystyle{ k}\) kolejnych liczb, więc istnieje bijekcja (powiedzmy \(\displaystyle{ f}\)) między czynnikami występującymy w mianowniku a czynnikami występującymi w liczniku, taka że \(\displaystyle{ x|f(x)}\) dla każdego argumentu \(\displaystyle{ x}\),

oraz

2. \(\displaystyle{ p^m}\) dzieli się tylko przez potęgi \(\displaystyle{ p}\) i wynik tego dzielenia zawsze będzie podzielny przez \(\displaystyle{ p}\) (bo w mianowniku na pewno nie znajdzie się \(\displaystyle{ p^m}\)), co implikuje tezę?

Czy dodatkowo prawdą będzie, że jeżeli \(\displaystyle{ k=p^r+s}\), to \(\displaystyle{ p^{m-r}\Big|{p^m \choose k}}\) ?

Edit:
Pospieszyłem się z punktem 1. Weźmy \(\displaystyle{ 5,6,7}\) oraz \(\displaystyle{ 1,2,3}\). Nie istnieje bijekcja, jakiej bym sobie życzył.

[Premislav]

Rozwiązanie nieelementarne:
mamy \(\displaystyle{ v_p(n!)= \sum_{j=1}^{ \infty } \left\lfloor \frac{n}{p^j}\right\rfloor}\)
gdzie dla liczby pierwszej \(\displaystyle{ p}\) i liczby całkowitej \(\displaystyle{ a}\) mamy \(\displaystyle{ v_p(a)=x \Leftrightarrow p^x|a\wedge p^{x+1}\nmid a}\).
Wobec tego jest
\(\displaystyle{ v_p((p^m)!)= \sum_{j=1}^{ \infty } \left\lfloor \frac{p^m}{p^j}\right\rfloor=p^{m-1}+p^{m-2}+\ldots+p+1}\)
a ponadto dla \(\displaystyle{ k=1, \ldots p^m-1}\) mamy
\(\displaystyle{ v_p(k!)= \sum_{j=1}^{ \infty } \left\lfloor \frac{k}{p^j}\right\rfloor\le \sum_{j=1}^{ \infty } \left\lfloor \frac{p^m-1}{p^j}\right\rfloor=p^{m-2}+p^{m-1}+\ldots+1}\)
oraz
\(\displaystyle{ v_p((p^m-k)!)= \sum_{j=1}^{ \infty } \left\lfloor \frac{p^m-k}{p^j}\right\rfloor\le \sum_{j=1}^{ \infty } \left\lfloor \frac{p^m-1}{p^j}\right\rfloor=p^{m-2}+p^{m-1}+\ldots+1}\),
a ponadto \(\displaystyle{ v_p(ab)=v_p(a)v_p(b)}\), więc
\(\displaystyle{ v_p((p^m)!)=p^{m-1}+p^{m-2}+\ldots+p+1}\)
oraz (tak naprawdę nierówność jest ostra)
\(\displaystyle{ v_p(k!(p^m-k)!}=v_p(k!)v_p((p^m-k)!) \le 2\left( p^{m-2}+p^{m-1}+\ldots+p+1\right)}\)
i pozostaje stwierdzić, że
\(\displaystyle{ 2\left( p^{m-2}+p^{m-1}+\ldots+p+1\right)=\\=2 \frac{p^{m-1}-1}{p-1} < \frac{p^{m}-1}{p-1}=p^{m-1}+p^{m-2}+\ldots+p+1=v_p\left( (p^m)!\right)}\)
a ta nierówność wynika w sposób oczywisty z warunku \(\displaystyle{ p\ge 2}\).

[Zahion]

\(\displaystyle{ {p^m \choose k} = {p^m - 1 \choose k - 1} \cdot \frac{p^{m}}{k}}\) - może bardziej w tym kierunku.

[Premislav]

No cóż…