Definition und erste Teilbarkeitseigenschaften

• Wegen $$ \sum_{k\geq 0}\binom{\alpha+1} k x^k = (1+x)^{\alpha+1} =(1+x)(1+x)^\alpha = \sum_{k\geq 0}\binom \alpha k x^k + \sum_{k\geq 0}\binom \alpha k x^{k+1} $$ gilt, dass $$ \binom{\alpha+1}{k+1} = \binom{\alpha}{k+1} + \binom{\alpha}{k}.$$
• Für $n\in \IN$ gilt $\binom nk \not=0$ genau dann, wenn $0\leq k \leq n$. In diesem Fall gilt $\binom nk = \frac {n!}{k!(n-k)!}$ und somit $\binom nk = \binom n{n-k}$.
• Eine endliche Menge mit $n$ Elementen hat genau $\binom nk$ Teilmengen mit $k$ Elementen. Insbesondere ist $\binom nk\in \IN$.
• Wegen $\binom n0 = \binom nn = 1$ und $\binom nk + \binom n{k+1} = \binom {n+1}{k+1}$, sind die Binomialkoeffizienten identisch zu den Einträgen im Pascalschen Dreieck: $$ \begin{array}{ccc} \binom00&&1\\ \binom10\quad\binom11&&1\qquad1\\ \binom20\quad\binom21\quad\binom22&&1\qquad2\qquad1\\ \binom30\quad\binom31\quad\binom32\quad\binom33&=&1\qquad3\qquad3\qquad1\\ \binom40\quad\binom41\quad\binom42\quad\binom43\quad\binom44&&1\qquad4\qquad6\qquad4\qquad1\\ \end{array} $$
• Es ist $\binom{-n}k = (-1)^k \binom{n+k-1}k$. Da $\binom{n+k-1}k$ die Anzahl der Möglichkeiten ist, $k$ nicht unterscheidbare Objekte an $n$ unterscheidbare Personen zu verteilen, ist insbesondere $\binom{-n}k \in \IZ$.
• Wegen $\binom{-n}0=1$, $\binom {-1}k = (-1)^k$ und $\binom{-n}{k} + \binom{-n}{k+1} = \binom{-(n-1)}{k+1} $ können wir auch die Binomialkoeffizienten $\binom{-n}k$ in einem Pascalschen Dreiecksschema anordnen: $$ \begin{array}{ccc} \binom{-5}0&& \phantom{-}1\\ \binom{-4}0 \quad \binom{-4}1 && \phantom{-}1 \quad -4\\ \binom{-3}0 \quad \binom{-3}1 \quad \binom{-3} 2 && \phantom{-}1 \quad -3 \quad \phantom{-}6\\ \binom{-2}0 \quad \binom{-2} 1 \quad \binom{-2}2 \quad \binom{-2}3 &=&\phantom{-} 1 \quad -2 \quad\phantom{-} 3 \quad -4\\ \binom{-1}0 \quad \binom{-1}1 \quad \binom{-1}2 \quad \binom{-1}3 \quad \binom{-1}4& &\phantom{-}1 \quad -1 \quad \phantom{-}1 \quad -1 \quad \phantom{-}1 \end{array}$$

Übungsaufgaben

1. Für $p$ prim, $m\in \IN$ und $1\leq k \leq p^m-1$ ist $\binom {p^m}k$ durch $p$ teilbar. \showon Beweis Zunächst betrachten wir den Fall $m=1$: Dann ist $\binom pk = \frac{p!}{k!(p-k)!}$. Der Zähler ist offenbar durch $p$ teilbar, der Nenner aber wegen $k \leq p-1$ und $p-k\leq p-1$ nicht. Also ist $\binom pk$ durch $p$ teilbar. Daraus folgt insbesondere, dass im Polynomring $\IF_p[x]$ die Gleichung $(1+x)^p = 1+x^p$ gilt. Mit vollständiger Induktion kann man folgern, dass sogar $(1+x)^{p^m} = 1+x^{p^m}\in \IF_p[x]$ gilt. Ein Koeffizientenvergleich mit $(1+x)^{p^m} = \sum_{k=0}^{p^m}\binom {p^m}kx^k$ liefert, dass $$ \binom {p^m}k \equiv 0 \pmod p$$ für $1\leq k\leq p^m-1$ gilt. \showoff
2. Für $p$ prim und $m\in \IN$ gilt $$ \binom{-p^m}k \equiv \begin{cases} (-1)^k, & \text{falls $k$ durch $p^m$ teilbar ist,}\\ 0, & \text{sonst}\end{cases} \pmod p.$$ \showon Beweis Wir rechnen in $\IF_p[[x]]$ und verwenden das Resultat aus der ersten Aufgabe: $$ (1+x)^{-p^m} = \frac 1{(1+x)^{p^m}} = \frac 1{1+x^{p^m}} = \sum_{k=0}^\infty (-1)^kx^{kp^m}$$ (Der letzte Schritt folgt aus der geometrischen Reihenformel $\frac 1{1-y} = 1+y+y^2+\ldots$ mit $y=-x^{p^m}$.) Ein Koeffizientenvergleich mit $$(1+x)^{-p^m} = \sum_{k=0}^\infty \binom{-p^m}k x^k$$ liefert wegen $(-1)^k \equiv (-1)^{kp^m}\pmod p$ die Behauptung. \showoff
3. Wenn wir das Pascalsche Dreieck modulo $p^e$ für $e\geq 1$ betrachten, dann stellen wir fest, dass die $p^{e+m}$-te Zeile für $m\geq 0$ aus der $p^{e-1}$-ten Zeile entsteht, indem man mit Nullen auffüllt. Beispiel für $p^e\in\{4,8,9\}$: $$\begin{array}{c|c|c|c} \text{Zeile} & \mod 4 &\mod 8& \mod 9\\ \hline 0&1&1&1\\ 1&1\quad1&1\quad1&1\quad1\\ 2&\color{blue}{1\quad2\quad1}&1\quad2\quad1&1\quad2\quad1\\ 3&1\quad3\quad3\quad1&1\quad3\quad3\quad1&\color{blue}{1\quad3\quad3\quad1}\\ 4&\color{blue}{1\quad0\quad2\quad0\quad1}&\color{red}{1\quad4\quad6\quad4\quad1}&1\quad4\quad6\quad4\quad1\\ 5&1\quad1\quad2\quad2\quad1\quad1&1\quad5\quad2\quad2\quad5\quad1&1\quad5\quad1\quad1\quad5\quad1\\ 6&1\quad2\quad3\quad0\quad3\quad2\quad1&1\quad6\quad7\quad4\quad7\quad6\quad1&1\quad6\quad6\quad2\quad6\quad6\quad1\\ 7&1\quad3\quad1\quad3\quad3\quad1\quad3\quad1&1\quad7\quad5\quad3\quad3\quad5\quad7\quad1&1\quad7\quad3\quad8\quad8\quad3\quad7\quad1\\ 8&\color{blue}{1\quad0\quad0\quad0\quad2\quad0\quad0\quad0\quad1}&\color{red}{1\quad0\quad4\quad0\quad6\quad0\quad4\quad0\quad1}&1\quad8\quad1\quad2\quad7\quad2\quad1\quad8\quad1\\ 9&1\quad1\quad0\quad0\quad2\quad2\quad0\quad0\quad1\quad1&1\quad1\quad4\quad4\quad6\quad6\quad4\quad4\quad1\quad1&\color{blue}{1\quad0\quad0\quad3\quad0\quad0\quad3\quad0\quad0\quad1} \end{array} $$ Allgemein gilt $$ \binom{p^{e+m}}{k} \equiv 0 \pmod{p^e},$$ falls $k$ nicht durch $p^{m+1}$ teilbar ist, und $$ \binom{p^{e+m}}{k} \equiv \binom{p^{e-1}}{k/p^{m+1}} \pmod{p^e},$$ sonst. \showon Beweis Per Induktion nach $e$ zeigen wir zunächst, dass $$ (1+x)^{p^e} \equiv (1+x^p)^{p^{e-1}} \pmod {p^e}$$ gilt:
   • Für $e=1$ haben wir in Aufgabe 1 gesehen, dass $$(1+x)^p\equiv 1+x^p\pmod p$$ gilt.
   • Angenommen die Aussage ist bereits für ein festes $e\geq 1$ gezeigt. Dann gibt es ein Polynom $y\in \IZ[x]$ mit ganzzahligen Koeffizienten, so dass $$ (1+x)^{p^e} = (1+x^p)^{p^{e-1}}+ p^ey$$ gilt. Also ist $$ \begin{align*} (1+x)^{p^{e+1}}& = ((1+x^p)^{p^{e-1}}+ p^ey)^p \\ &= (1+x^p)^{p^{e}}+ \binom p1 p^ey(1+x^p)^{p^{e-1}(p-1)}+ \binom p2 p^{2e}y^2(1+x^p)^{p^{e-1}(p-2)}+ \ldots +p^{pe}y^p \end{align*}$$ Da $\binom pk$ für $1\leq k \leq p-1$ durch $p$ teilbar ist, sind alle Summanden bis auf den ersten durch $p^{e+1}$ teilbar. Also ist $$ (1+x)^{p^{e+1}}\equiv (1+x^p)^{p^{e}} \pmod {p^{e+1}},$$ womit der Induktionsschluss geglückt ist.
   Eine weitere Induktion nach $m$ zeigt, dass $$ (1+x)^{p^{e+m}} \equiv (1+x^{p^{m+1}})^{p^{e-1}} \pmod {p^e}$$ gilt, woraus durch Koeffizientenvergleich beider Seiten die Behauptung folgt. \showoff
4. Für $e\geq 1$ und $m\geq 0$ gilt $$ \binom{-p^{e+m}}{k} \equiv 0 \pmod{p^e},$$ falls $k$ nicht durch $p^{m+1}$ teilbar ist, und $$ \binom{-p^{e+m}}{k} \equiv \binom{-p^{e-1}}{k/p^{m+1}} \pmod{p^e},$$ sonst. \showon Beweis Aus dem Beweis der vorherigen Aufgabe folgt unmittelbar, dass $$ (1+x)^{-p^{e+m}} = (1+x^{p^{m+1}})^{-p^{e-1}} = \sum_{k\geq 0}\binom{-p^{e-1}}k x^{kp^{m+1}} \in (\IZ/p^e)[[x]], $$ woraus die Behauptung folgt. \showoff

Übungsaufgaben

1. Mit welchem Rest ist $\binom{2022}{256}$ durch $17$ teilbar? \showon Lösung Es ist $2022 = [6,16,16]_{17}$ und $256 =[0,15,1]_{17}$. Also gilt $$ \binom{2022}{256} \equiv \binom 60 \binom {16}{15}\binom{16}1 \equiv 16\cdot 16 \equiv (-1)^2 \equiv 1 \pmod{17}$$ \showoff
2. In jeder Zeile des Pascalschen Dreiecks ist die Anzahl der ungeraden Einträge eine Zweierpotenz. \showon Beweis Aus dem Korollar zum Satz von Lucas folgt, dass es zu gegebenem $n=[n_m,\ldots, n_0]_p\in \IN$ genau $$(n_0+1)(n_1+1)\cdots (n_m+1)$$ natürliche Zahlen $k$ gibt, für die $\binom nk$ nicht durch $p$ teilbar ist. Für $p=2$ ist $n_i\in \{0,1\}$, also ist das Produkt $(n_0+1)\cdots (n_m+1)$ eine Zweierpotenz. \showoff
3. Löse meine Knobelaufgabe hier.
4. 1. Der Satz von Lucas stellt modulo $p$ eine Beziehung zwischen $\binom nk$ und $\binom{n_i}{k_i}$ für die $p$-adischen Ziffern von $n$ und $k$ her. Gilt die dazu analoge Beziehung auch zwischen $\binom{-n}k$ und $\binom{-n_i}{k_i}$?
   2. Für eine natürliche Zahl $n$ sei $\pi_p(n)$ definiert als die Anzahl aller Möglichkeiten $n$ in eine Summe von Potenzen von $p$ zu partitionieren. D.h.$\pi_p(n)$ ist die Anzahl aller Folgen $n_0,n_1,\ldots \in \IN$ mit $\lim_{i\to \infty} n_i = 0$ und $n = n_0+n_1p+ n_2p^2+\ldots$. Zeige, dass wenn $k=[k_m, \ldots, k_0]_p$ eine $p$-adische Darstellung von $k\in \IN$ ist, dann gilt $$ \pi_p(k) \equiv (k_1+1)(k_2+1)\cdots (k_m+1) \pmod p$$
   \showon Lösung
   1. \showon Nein, die gilt nicht. Z.B. ist $\binom{-1}2 = 1 $, und für $1 = [0,1]_2, 2 = [1,0]_2$ gilt daher $$ \binom{-[0,1]_2}{[1,0]_2} \not\equiv \binom{-0}1 \binom{-1}0 \equiv 0 \pmod 2.$$ Sehen wir uns an, wo der Beweis schief geht: In $\IF_p[[x]]$ gilt $$ \begin{align*} (1+x)^{-n} &= (1+x)^{-n_0}(1+x^p)^{-n_1}(1+x^{p^2})^{-n_2}\cdots (1+x^{p^m})^{-n_m}\\ &=\sum_{\ell_0\geq 0}\binom{-n_0}{\ell_0}x^{\ell_0} \cdot \sum_{\ell_1\geq 0}\binom{-n_1}{\ell_1}x^{\ell_1p} \cdot \sum_{\ell_2\geq 0}\binom{-n_2}{\ell_2}x^{\ell_2p^2} \cdots \sum_{\ell_m\geq 0}\binom{-n_m}{\ell_m}x^{\ell_mp^m} \\ &= \sum_{\ell_0,\ell_1,\ldots, \ell_m \geq 0} \binom{-n_0}{\ell_0}\binom{-n_1}{\ell_1}\cdots \binom{-n_m}{\ell_m}x^{\ell_0+\ell_1p+\ldots \ell_mp^m} \end{align*}$$ So weit, so gut. Im Gegensatz zum Beweis des Satzes von Lucas, haben wir hier aber nicht die Bedingung $\ell_i \leq n_i$. Wir können daher lediglich schlussfolgern, dass $$ \binom{-n}{k} \equiv \sum_{\substack{k_0,k_1,\ldots k_m \geq 0 \\ k=k_0+k_1p+\ldots+k_mp^m}}\binom{-n_0}{k_0}\binom{-n_1}{k_1}\cdots\binom{-n_m}{k_m} \pmod p.$$ \showoff
   2. \showon Beweis Wenn $k=[k_m,\ldots, k_0]_p$, dann gilt insbesondere $k < p^{m+1}$. In jeder Darstellung von $k$ als Summe von Potenzen von $p$ können also nur Potenzen $p^\ell$ mit $0\leq \ell\leq m$ als Summanden vorkommen. Sei $n:=1+p+p^2+\ldots p^{m} = [1,1,\ldots,1]_p$. Mit der in a) hergeleiteten Formel gilt dann, dass $$ \begin{align*}\binom{-n}{k} &\equiv \sum_{\substack{k_0',k_1',\ldots k_m' \geq 0 \\ k=k_0'+k_1'p+\ldots+k_m'p^m}}\binom{-1}{k_0'}\binom{-1}{k_1'}\cdots\binom{-1}{k_m'} \\[1ex] &\equiv \sum_{\substack{k_0',k_1',\ldots k_m' \geq 0 \\ k=k_0'+k_1'p+\ldots+k_m'p^m}}(-1)^{k_0'}(-1)^{k_1'}\cdots (-1)^{k_m'}\\[1ex] & \equiv \sum_{\substack{k_0',k_1',\ldots k_m' \geq 0 \\ k=k_0'+k_1'p+\ldots+k_m'p^m}}(-1)^{k_0'}(-1)^{k_1'p}\cdots (-1)^{k_m'p^m}\\[1ex] &\equiv \sum_{\substack{k_0',k_1',\ldots k_m' \geq 0 \\ k=k_0'+k_1'p+\ldots+k_m'p^m}}(-1)^{k_0'+k_1'p+\ldots+k_m'p^m}\\[1ex] &\equiv \sum_{\substack{k_0',k_1',\ldots k_m' \geq 0 \\ k=k_0'+k_1'p+\ldots+k_m'p^m}}(-1)^{k}\\[1ex] &\equiv (-1)^k\pi_p(k) \pmod p \end{align*}$$ Andererseits gilt $$\binom {-n}k = (-1)^k\binom {n+k-1}k = (-1)^k \binom{k_0 + (k_1+1)p + (k_2+1)p^2+\ldots +(k_m+1)p^m}{k_0+k_1p+k_2p^2\ldots k_mp^m}$$ Wenn $k_i +1\leq p-1$ für $i=2,\ldots, m$, dann gilt nach dem Satz von Lucas $$\begin{align*} \binom{-n}k &\equiv (-1)^k \binom {k_0}{k_0}\binom{k_1+1}{k_1}\binom{k_2+1}{k_2}\cdots \binom {k_m+1}{k_m}\\ &\equiv (-1)^k (k_1+1)(k_2+1)\cdots (k_m+1)\pmod p. \end{align*} $$ Wenn nicht, dann gibt es ein kleinstes $i\geq 1$ mit $k_i+1 = p$. Die $p$-adische Darstellung von $n+k-1$ hat dann an der zur Potenz $p^i$ gehörenden Stelle die Ziffer $0$, während $k_i >0$ gilt. Aus dem Korollar folgt demnach $$\binom{-n}k \equiv 0 \equiv (-1)^k(k_1+1)(k_2+1)\cdots (k_m+1)\pmod p. $$ Insgesamt haben wir gezeigt, dass $$ \pi_p(k) \equiv (-1)^k \binom{-n}k \equiv (k_1+1)(k_2+1)\cdots (k_m+1) \pmod p.$$ \showoff
\showoff

• Durch Koeffizientenvergleich für $0\leq k\leq p^m-\ell$ folgt der Satz.
• Für $p^m-\ell+1 \leq k\leq p^m-1$ erhalten wir $$ \binom{-\ell}k \equiv 0 \pmod p.$$ Diese Aussage hätten wir auch mit dem Satz von Lucas herleiten können: Im Binomialkoeffizienten $\binom{-\ell}k = (-1)^k\binom{k+\ell-1}{\ell-1}$ spielen modulo $p$ wegen $\ell-1 < p^m$ nur die hinteren $m$ $p$-adischen Stellen von $k+\ell-1$ eine Rolle. Und da $0\leq k+\ell -1-p^m < \ell -1$ gilt, können wir das Korollar zum Satz von Lucas anwenden.
• Für $k\geq p^m$ erhalten wir $$ \binom{-\ell}k \equiv - \binom{-\ell}{k-p^m}\pmod p.$$ Auch das ist eine Konsequenz aus dem Satz von Lucas: Die Kongruenz ist äquivalent zu $\binom{k+\ell-1}{\ell-1} \equiv \binom{k+\ell-1 -p^m}{\ell-1}\pmod p$. Da $\ell-1< p^m$ ist, spielt es modulo $p$ keine Rolle, ob im Zähler des Binomialkoeffizienten $k+\ell-1$ der $k+\ell-1-p^m$ steht.

Übungsaufgaben

1. Mit welchem Rest ist $\binom{16}9$ durch $19$ teilbar? \showon Lösung $$ \binom{16}9 = \binom{19-3}7 \equiv \binom {-3}7 \equiv (-1)^7\binom 97 \equiv - \binom 92 \equiv - 36 \equiv 2 \pmod {19} $$ \showoff
2. Für $r\in \IZ$ sei $$M_r:=\left\{(n,k)\in \IN^2 \mid 0\leq k \leq n< p ~\text{und}~ {\binom n k}^2 \equiv r \pmod p\right\}.$$ Dann gilt:
   • Falls $p\not\equiv 1 \pmod 3$ ist, dann ist $|M_r|$ für jedes $r$ durch $3$ teilbar.
   • Falls $p\equiv 1 \pmod 3$ ist, dann gibt es genau ein $r\in\IN$ mit $0\leq r < p$, für dass $|M_r|$ nicht durch drei teilbar ist. Für dieses $r$ gilt $|M_r|\equiv 1 \pmod 3$.
   \showon Beweis $$ \begin{array}{c|c|c} n&\binom nk ^2 \mod 7 & \binom nk ^2 \mod {11}\\ \hline 0&1&1\\ 1&1\quad1&1\quad1\\ 2&1\quad4\quad1&1\quad4\quad1\\ 3&1\quad2\quad2\quad1&1\quad9\quad9\quad1\\ 4&1\quad2\quad1\quad2\quad1&1\quad5\quad3\quad5\quad1\\ 5&1\quad4\quad2\quad2\quad4\quad1&1\quad3\quad1\quad1\quad3\quad1\\ 6&1\quad1\quad1\quad1\quad1\quad1\quad1&1\quad3\quad5\quad4\quad5\quad3\quad1\\ 7&&1\quad5\quad1\quad4\quad4\quad1\quad5\quad1\\ 8&&1\quad9\quad3\quad1\quad5\quad1\quad3\quad9\quad1\\ 9&&1\quad4\quad9\quad5\quad3\quad3\quad5\quad9\quad4\quad1\\ 10&&1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\\ \end{array} $$ Die Kongruenz $$ \binom nk = \binom{p-(p-n)}{n-k} \equiv \binom{-(p-n)}{n-k} \equiv (-1)^{n-k}\binom {p-k-1}{n-k} \pmod p$$ zeigt, dass $(n,k)\in M_r$ genau dann gilt, wenn $(p-k-1,n-k)\in M_r$. Die Abbildung $\tau:(n,k)\mapsto (p-k-1,n-k)$ erfüllt $\tau^3(n,k)=\tau(\tau(\tau(n,k))) =(n,k)$ und beschreibt anschaulich eine Dritteldrehung der obersten $p$ Zeilen des Pascalschen Dreiecks. Die Menge $M_r$ lässt sich demnach in disjunkte Teilmengen der Form $\{(n,k), \tau(n,k), \tau^2(n,k)\}$ zerlegen. Also ist $|M_r|$ nur dann nicht durch drei teilbar, wenn $\tau$ einen Fixpunkt $(n,k)$ hat (das Drehzentrum) und $r\equiv \binom nk ^2\pmod p$ gilt. Ein Fixpunkt $(n,k)$ von $\tau$ müsste die Gleichung $(n,k) = (p-k-1,n-k)$ erfüllen, was dann und nur dann möglich ist, wenn $n=2k$ und $p=3k+1$ gilt. \showoff

• Für eine reelle Zahl $x\in \IR$ sei $\lfloor x\rfloor\in \IZ$ definiert als die diejenige ganze Zahl, für die $\lfloor x\rfloor \leq x < \lfloor x\rfloor +1$ gilt.
• Für $n=[n_m,n_{m-1},\ldots, n_0]_p$ sei $Q_p(n):=n_0+n_1+\ldots+n_m$ die $p$-adische Quersumme von $n$.

Übungsaufgaben

1. Bestimme die größte Potenz von $45$, die ein Teiler von $2022!$ ist. \showon Lösung Es ist $45=3^2\cdot 5$. Wir berechnen daher mit der Formel von Legendre: $$ \begin{align*} \nu_3(2022!) &= 674+224+74+24+8+2 &= 1006\\ \nu_5(2022!) &= 404+80+16+3 &= 503 \end{align*}$$ Wegen $$ \min\left\{\left\lfloor\frac{\nu_3(2022!)}2\right\rfloor, \nu_5(2022!\right\} = 503$$ ist $45^{503}$ die gesuchte Potenz. \showoff
2. Beweise für $0\leq k\leq n$ die Kürzungsregel $\nu_p(\binom {pn}{pk}) = \nu_p(\binom nk)$ \showon Beweis Aus der Formel von Legendre folgt, dass $$ \begin{align*} \nu_p\left(\binom nk\right) &= \nu_p(n!) - \nu_p(k!) - \nu_p((n-k)!)\\ &= \frac{n-Q_p(n)}{p-1} - \frac{k-Q_p(k)}{p-1} - \frac{n-k-Q_p(n-k)}{p-1}\\ &= \frac{Q_p(k)+Q_p(n-k)-Q_p(n)}{p-1}. \end{align*}$$ Da sich die $p$-adische Quersumme einer natürlichen Zahl bei Multiplikation mit $p$ nicht ändert, folgt die Behauptung. \showoff
3. Für welche $n\in \IN$ ist $\binom{2n}n$ durch $4$ teilbar? \showon Lösung Es ist $$ \nu_2\left(\binom{2n}n\right)= 2Q_2(n)-Q_2(2n) = Q_2(n).$$ $\binom{2n}n$ ist also nur dann nicht durch $4$ teilbar, wenn $Q_2(n)\leq 1$ gilt, d.h. wenn $n$ eine Zweierpotenz oder $n=0$ ist. \showoff
4. Bestimme für jede Primzahl $p$ alle natürlichen Zahlen $n\geq 1$, für die $\nu_p(n!)\geq\lfloor\frac {n-1}{p-1}\rfloor$ gilt. \showon Lösung Wegen $$\nu_p(n!) = \frac{n-Q_p(n)}{p-1}\leq \frac{n-1}{p-1}$$ ist $\nu_p(n!)\leq \lfloor \frac {n-1}{p-1}\rfloor$ für alle $n\geq 1$. Gesucht sind also diejenigen $n$, für die Gleichheit gilt. 1. Fall: $p=2$ Dann muss $n-Q_2(n) = n-1$ gelten, was genau dann der Fall ist, wenn $n$ eine Potenz von $2$ ist. 2. Fall: $p\geq 3$ Sei $q:= Q_p(n)$ und es sei $r$ der Rest, den $n-1$ bei Division durch $p-1$ lässt. D.h. $0\leq r \leq p-2$ und es existiert ein $x\in \IN$ mit $n-1 = x(p-1)+r$. Dann ist $$ \begin{align*} &&\nu_p(n!) &= \lfloor \frac {n-1}{p-1}\rfloor \\ \iff&& \frac {(p-1)x+r+1 -q}{p-1} &= x \\ \iff && q &= r+1 \end{align*}$$ Da außerdem $$ q \equiv n \equiv r+1 \pmod {p-1}$$ gilt, können wir schlussfolgern, dass $\nu_p(n!) = \lfloor\frac{n-1}{p-1}\rfloor$ genau dann gilt, wenn $Q_p(n)\leq p-1$. \showoff

Übungsaufgaben

1. Bestimme die größte Potenz von $5$, die ein Teiler von $\binom{2022}{918}$ ist. \showon Lösung Es ist $2022 = [3,1,0,4,2]_5$ und $918 = [1,2,1,3,3]_5$. Bei der Berechnung von $2022-918$ $\backslash begin\{array\}\{r\}\; [3,1,0,4,2]\_5\backslash \backslash \; -[\backslash mathclap\{\backslash underset\; 11\},\{\backslash underset12\},1,\{\backslash underset13\},3]\_5\backslash \backslash \; \backslash hline\; [1,3,4,0,4]\_5\; \backslash end\{array\}$ kommt es im $5$-adischen Stellenwertsystem zu genau $3$ Überträgen. Also ist $\binom{2022}{918}$ durch $5^3$ teilbar, aber nicht durch $5^4$. \showoff
2. 1. Wenn $n$ und $k$ teilerfremd sind, dann ist $\binom{-n}k$ durch $n$ teilbar.
   2. Die Catalanzahlen $C_n:=\frac 1{n+1}\binom {2n}n$ sind ganz.
   \showon Lösung
   1. \showon Beweis mit Satz von Kummer Zu zeigen ist, dass $\binom{n+k-1}{k}=\binom{n+k-1}{n-1}$ durch $n$ teilbar ist. Das ist äquivalent dazu, dass $\nu_p(n)\leq \nu_p(\binom{n+k-1}{n-1})$ für jeden Primteiler $p$ von $n$ gilt. Sei $r:=\nu_p(n)$. Dann endet die $p$-adische Darstellung von $n$ auf genau $r$ Nullen, und somit hat die $p$-adische Darstellung von $n-1$ die Form $n-1= [n_m,n_{m-1},\ldots, n_r, p-1, p-1,\ldots, p-1]_p$ mit $r$ Ziffern $p-1$ am Ende. Da $n$ und $k$ teilerfremd sind, also insbesondere $p$ kein Teiler von $k$ ist, ist die letzte Ziffer der $p$-adischen Darstellung von $k$ nicht Null. Somit kommt es bei der Addition von $n-1$ und $k$ im $p$-adischen System zu mindestens $r$ Überträgen. Folglich ist $\nu_p(\binom{n+k-1}{n-1})\geq r$. \showoff \showon Kombinatorischer Beweis Es sei $M$ die Menge aller $n$-Tupel $(k_1,\ldots, k_n)\in \IN^n$ mit $k=k_1+\ldots+k_n$. Dann ist $|M|=|\binom{-n}k|$. Betrachte die Abbildung $f:M\to M, (k_1,\ldots, k_n) \mapsto (k_2,\ldots, k_n,k_1)$. Offenbar gilt $f^n=\id_M$. Sei $m:=(k_1,\ldots, k_n)\in M$. Es sei $d\geq 1$ minimal mit der Eigenschaft $f^d(m)=m$. Dann ist $d$ ein Teiler von $n$ und es gilt $k_i=k_j$, wenn $i\equiv j\pmod d$ für $1\leq i,j\leq n$. Daraus folgt $k = k_1+\ldots+k_n = \frac nd(k_1+k_2+\ldots+k_d)$. Also ist $\frac nd$ ein Teiler von $k$ und somit muss $d=n$ sein. Es folgt, dass für alle $m\in M$ die Menge $\{m,f(m),\ldots, f^{n-1}(m)\}$ genau $n$ Elemente hat. Da $f$ injektiv ist, können wir $M$ als disjunkte Vereinigung von Teilmengen der Form $\{m, f(m),f^2(m),\ldots, f^{n-1}(m)\}$ mit $m\in M$ schreiben. Also ist $|M|$ durch $n$ teilbar. \showoff
   2. \showon Beweis Üblicherweise zeigt man das, indem man die Gleichung $C_n = \binom{2n}n -\binom{2n}{n+1}$ nachrechnet. Da $n$ und $n+1$ teilerfremd sind, können wir alternativ wegen a) aus $\binom{-(n+1)}n = (-1)^n \binom{2n}n$ schließen, dass $\binom{2n}n$ durch $n+1$ teilbar ist. \showoff
   \showoff
   3. Der größte gemeinsame Teiler von $\binom n1,\ldots,\binom n{n-1}$ ist $1$ oder eine Primzahl. \showon Beweis Wegen $\binom n1 = n$ ist der größte gemeinsame Teiler $d$ von $\binom n1,\ldots \binom n{n-1}$ ein Teiler von $n$. 1. Fall: $n=p^m$ für eine Primzahl $p$ und $m\geq 1$. Dann ist $n=[1,0,0,\ldots,0]_p$. Für $k:=p^{m-1}=[0,1,0,\ldots, 0]_p$ kommt es bei der Berechnung $\backslash begin\{array\}\{r\}\; [1,\backslash phantom\{p-\{\}\}0,0,\backslash ldots,0]\_p\backslash \backslash \; -[\backslash mathclap\{\backslash underset\; 10\},\backslash phantom\{p-\{\}\}1,0,\backslash ldots,0]\_p\backslash \backslash \; \backslash hline\; [0,p-1,0,\backslash ldots,0]\_p\; \backslash end\{array\}$ zu genau einem Übertrag, also gilt $\nu_p\left(\binom nk\right) = 1$. Somit ist $d=p$. 2. Fall: $n$ ist keine Primzahlpotenz. Dann hat für jeden Primteiler $p$ von $n$ die $p$-adische Darstellung von $n$ mindestens zwei Nichtnullziffern. Sei etwa $n=[n_m,n_{m-1},\ldots, n_j,\ldots, n_0]_p$ mit $n_m\not=0\not=n_j$ und $m>j>0$ (es gilt $n_0=0$, also können wir $j>0$ annehmen). Für $k:=n-n_jp^j =[n_m,n_{m-1},\ldots, 0,\ldots, n_0]_p$ ist $1\leq k\leq n-1$ und die übertragsfreie Rechnung $\backslash begin\{array\}\{r\}\; [n\_m,n\_\{m-1\},\backslash ldots,\; n\_j,\backslash ldots,\; n\_0]\_p\backslash \backslash \; -[n\_m,n\_\{m-1\},\backslash ldots,\; 0\_\{\backslash phantom\{j\}\},\backslash ldots,\; n\_0]\_p\backslash \backslash \; \backslash hline\; [\; n\_j,\backslash ldots,\; \backslash mathclap\{0\_\{\backslash phantom\; 0\}\}]\_p\; \backslash end\{array\}$ zeigt, dass $ \binom nk$ nicht durch $p$ teilbar ist. Also gilt $d=1$. \showoff
   4. 1. Sei $0\leq k \leq n$. Zeige, dass das kleinste gemeinsame Vielfache von $1,2,3,\ldots,n$ durch $\binom nk$ teilbar ist.
      2. Berechne den Quotienten $$ \frac{\opn{kgV}(1,2,\ldots, n)}{\opn{kgV}(\binom n0,\binom n1, \binom n2,\ldots, \binom nn)} $$ in Abhängigkeit von $n$.
      \showon Lösung Sei $a:= \opn{kgV}(1,\ldots, n)$. Für jede Primzahl $p$ ist dann $\nu_p(a)=m_p$, wobei $m_p$ die größte ganze Zahl ist, für die $p^{m_p}\leq n$ gilt. Somit ist $p^{m_p} \leq n < p^{m_p+1}$.
      1. \showon Beweis Die $p$-adische Darstellung von $n$ hat die Länge $m_p+1$. Daher kommt es bei Addition von $k$ und $n-k$ im $p$-adischen System zu höchstens $m_p$ Überträgen. Also ist $\nu_p(\binom nk) \leq m_p =\nu_p(a)$ für alle Primzahlen $p$, d.h. $a$ ist durch $\binom nk$ teilbar. \showoff
      2. \showon Ergebnis $$ \frac{\opn{kgV}(1,2,\ldots, n)}{\opn{kgV}(\binom n0,\binom n1, \binom n2,\ldots, \binom nn)} = \begin{cases} q^{m}, & \text{falls }n+1= q^{m+1}\text{ für eine Primzahl }q,\\ n+1, &\text{sonst.}\end{cases}$$ \showoff \showon Beweis Sei $b:=\opn{kgV}(\binom n0,\binom n1, \binom n2,\ldots, \binom nn)$. Wir berechnen $\nu_p(\frac a b)$ für jede Primzahl $p$. 1. Fall: $n+1$ ist eine Potenz von $p$, d.h. $n+1=p^{m_p+1}$. Dann ist $n = [p-1,p-1,\ldots, p-1]_p$ und daher kommt es für kein $k\leq n$ bei der Berechnung der Differenz von $n$ und $k$ zu einem Übertrag, d.h. $\nu_p(b)=0$. Somit ist $\nu_p(\frac a b) = m_p = \nu_p(n+1)-1$. 2. Fall: $n+1$ ist keine Potenz von $p$. Sei $r:=\nu_p(n+1)$ und $m:=m_p$. Dann ist $n=[n_m,n_{m-1},\ldots, n_r, p-1, p-1,\ldots, p-1]_p$ mit $n_r\leq p-2$ und $n_m\geq 1$. Für $k\leq n$ kommt es daher bei der Berechnung der Differenz von $n$ und $k$ zumindest in den letzten $r$ Stellen zu keinem Übertrag. Somit ist $\nu_p(\binom nk)\leq m-r$. Speziell für $k:= n-p^m +p^r = [n_m-1,n_{m-1},\ldots ,n_{r+1}, n_r+1, p-1, p-1,\ldots, p-1]_p$ wird diese obere Grenze von $m-r$ Überträgen auch angenommen: Somit ist $\nu_p(b)=m-r$, also $\nu_p(\frac ab) = m-(m-r) = \nu_p(n+1)$. Da es höchstens eine Primzahl $p$ gibt, für die der erste Fall eintritt, folgt die Behauptung. \showoff
      \showoff
   
   
   [Edit]

   Abschließende Worte

   Auf den Satz von Kummer bin ich ursprünglich im Zusammenhang mit einer Frage von Wally hier im Forum gestoßen. Die zahlreichen Anwendungen, die Dorel Mihet in seinem sehr lesenswerten Artikel Legendre's and Kummer's Theorems Again beschrieben hat, sind meine Hauptquelle und haben mich motiviert nach 14 Jahren MP-Mitgliedschaft auch endlich mal einen Artikel zu schreiben.
   
   [Edit]
   \(\endgroup\)
   [Show outline only]