Mathematik: Teilbarkeit von Binomialkoeffizienten durch Primzahlen und Primzahlpotenzen
Released by matroid on Mi. 23. Februar 2022 18:00:03 [Statistics]
Written by Nuramon - 419 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)

Teilbarkeit von Binomialkoeffizienten durch Primzahlen und Primzahlpotenzen

Die Aussage, dass für eine Primzahl $p$ der Binomialkoeffizient $\binom pk$ für $1\leq k \leq p-1$ durch $p$ teilbar ist, ist für die meisten auf dem Matheplaneten wohl nicht neu. Weniger bekannt dürfte sein, wie man für einen beliebigen Binomialkoeffizienten $\binom nk$ effizient herausfinden kann, mit welchem Rest er durch $p$ teilbar ist, oder wie man die größte Potenz von $p$ findet, die $\binom nk$ teilt. Die Antworten auf diese Fragen liefern die Sätze von Lucas und Kummer, die wir in diesem Artikel herleiten werden. Indem wir auch die Binomialkoeffizenten $\binom {-n}k$ betrachten, werden sich zudem noch weitere Zusammenhänge offenbaren.
  • Definition und erste Teilbarkeitseigenschaften
  • Der Satz von Lucas
  • Eine Symmetrie im Pascalschen Dreieck
  • Die Formel von Legendre
  • Der Satz von Kummer
  • Abschließende Worte


Definition und erste Teilbarkeitseigenschaften

Für $\alpha \in \IR$ und $k\in \IN$ definieren wir die Binomialkoeffizienten $\binom \alpha k\in \IR$ als die in der Potenzreihenentwicklung von $(1+x)^\alpha\in\IR[[x]]$ auftretenden Koeffizienten von $x^k$: $$ (1+x)^\alpha = \sum_{k=0}^\infty \binom \alpha k x^k.$$ Explizit bedeutet das, dass $$ \binom \alpha k = \frac {\alpha(\alpha-1)(\alpha-2)\cdots (\alpha - (k-1))}{k!}.$$ Für diesen Artikel ist nur der Fall $\alpha \in \IZ$ relevant. Im gesamten Artikel bezeichnen $n$ und $k$ natürliche Zahlen und $p$ eine Primzahl. Hier ist eine Zusammenfassung der wichtigsten Eigenschaften von Binomialkoeffizienten:
  • 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

Der Satz von Lucas

Bisher haben wir nur Aussagen über $\binom nk \mod p$ getroffen, wenn $|n|$ eine Potenz von $p$ ist. Der Satz von Lucas wird uns für beliebige $n\geq 0$ erlauben, den Rest von $\binom nk$ modulo $p$ mit Hilfe der $p$-adischen Ziffern von $n$ und $k$ zu berechnen. Dazu erinnern wir uns zunächst, dass für jede natürliche Zahl $n$ und jede Basis $b\in \IN, b \geq 2$ genau ein $m\in \IN$ und eine Folge $n_0,n_1,\ldots, n_m$ mit $0\leq n_i \leq b-1$ für $i=0,\ldots, m$ und $n_m \geq 1 \lor m=0$ existiert, für die $$n = n_0 + n_1b+ n_2b^2+\ldots +n_mb^m$$ gilt. Wir nennen die $n_i$ die $b$-adischen Ziffern von $n$ und notieren diesen Zusammenhang als $$ n = [n_m, n_{m-1},\ldots, n_1, n_0]_b.$$ Da es manchmal praktisch ist, werden wir in dieser Notation auch führende Nullen zulassen, so dass z.B. $$2022 = [2,0,2,2]_{10} = [0,2,0,2,2]_{10} = [0,0,2,0,2,2]_{10} = \ldots$$ gilt.
Satz von Lucas. Es seien $n=[n_m,n_{m-1},\ldots, n_0]_p$ und $k=[k_m,k_{m-1},\ldots, k_0]_p$ $p$-adische Darstellungen der natürlichen Zahlen $n,k\geq 0$. Dann gilt $$ \binom nk \equiv \binom{n_0}{k_0}\binom{n_1}{k_1}\binom{n_2}{k_2}\cdots \binom{n_m}{k_m}\pmod p$$
Beweis: In $\IF_p[x]$ gilt $(x+1)^p = x^p+1$ und somit $(x+1)^{p^\ell}= (x^{p^\ell}+1)$ für $\ell\in \IN$. Damit folgt $$ \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=0}^{n_0}\binom{n_0}{\ell_0}x^{\ell_0} \cdot \sum_{\ell_1=0}^{n_1}\binom{n_1}{\ell_1}x^{\ell_1p} \cdot \sum_{\ell_2=0}^{n_2}\binom{n_2}{\ell_2}x^{\ell_2p^2} \cdots \sum_{\ell_m=0}^{n_m}\binom{n_m}{\ell_m}x^{\ell_mp^m} \\ &= \sum_{\substack{\ell_0,\ell_1,\ldots, \ell_m\\ 0\leq \ell_i \leq n_i}} \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*}$$ Ein Koeffizientenvergleich mit $$ (1+x)^n = \sum_{\ell=0}^n \binom n\ell x^\ell$$ liefert wegen der Eindeutigkeit von $p$-adischen Darstellungen die Behauptung. $\square$ Der Vollständigkeit halber sei erwähnt, dass man den Satz von Lucas auch gruppentheoretisch/kombinatorisch beweisen kann. Siehe z.B. hier. Wie man diesen Beweis verallgemeinern kann, um die Aussage $$ \binom nk \equiv c(n,k) + \sum_{i\geq 1}n_i \sum_{l=1}^{p-1}\binom pl c(n-p^i, k- lp^{i-1}) \pmod{p^2}$$ mit $c([a_m, a_{m-1},\ldots, a_0]_p,[b_m,b_{m-1},\ldots, b_0]_p):= \binom{a_0}{b_0} \cdots \binom{a_m}{b_m}$ zu erhalten, habe ich hier beschrieben. Da $\binom {n_i}{k_i} = 0$ für $k_i > n_i$ gilt und $\binom {n_i}{k_i}$ für $0\leq k_i \leq n_i\leq p-1$ nicht durch $p$ teilbar ist, haben wir folgende bemerkenswerte Folgerung aus dem Satz von Lucas:
Korollar. Für $n=[n_m,\ldots, n_0]_p$ und $k=[k_m,\ldots, k_0]_p$ ist $\binom nk$ genau dann durch $p$ teilbar, wenn es ein $i\in \{0,1,\ldots, m\}$ mit $n_i < k_i$ gibt.
Der Satz von Kummer, den wir später noch behandeln werden, stellt eine Verallgemeinerung dieses Korollars dar.

Ü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.
    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
  4. \showoff

Eine Symmetrie im Pascalschen Dreieck

Der Satz von Lucas vereinfacht die Berechnung von $\binom nk \mod p$ enorm. Allerdings sind selbst die Binomialkoeffizienten $\binom {n_i}{k_i}$ mit $n_i,k_i\leq p-1$ in der Regel zu groß um sie von Hand zu berechnen. Die Betrachtungen in diesem Abschnitt können manchmal dabei helfen, diese Berechnungen zu vereinfachen. Wir wissen bereits, dass für $m\geq 1$ in der $p^m$-ten Zeile des Pascalschen Dreiecks bis auf die beiden $1$-en am Rand alle Einträge durch $p$ teilbar sind. Indem wir rückwärts rechnen, können wir darauf schließen, wie die $p^m-1$-te Zeile modulo $p$ aussieht: $$\begin{array}{c|c} p^m-1 & \phantom{-}1 \quad {-}1\quad \phantom{-}1 \quad {-}1\quad \phantom{-}1 \\ p^m & \phantom{-}1 \quad \phantom{-}0 \quad \phantom{-}0 \quad \phantom{-}0 \quad \phantom{-}0 \quad \phantom{-}1 \end{array}$$ Wir halten fest: $$ \binom{p^m-1}k \equiv (-1)^k\pmod p$$ Wenn wir noch weiter rechnen, erhalten wir $$ \begin{array}{c|c} p^m-5& \phantom{-}1\\ p^m-4 & \phantom{-}1 \quad {-}4 \\ p^m-3 &\phantom{-}1 \quad {-}3 \quad \phantom{-}6\\ p^m-2 & \phantom{-}1 \quad {-}2 \quad \phantom{-}3 \quad {-}4\\ p^m-1 & \phantom{-}1 \quad {-}1\quad \phantom{-}1 \quad {-}1\quad \phantom{-}1 \end{array}$$ Darin erkennen wir die einprägsame Formel:
Satz. Für $m\geq 1$, $1\leq \ell\leq p^m$ und $0\leq k \leq p^m-\ell$ gilt $$ \binom {p^m-\ell}k \equiv \binom{-\ell}k \pmod p$$
Wir geben noch einen alternativen Beweis für $m=1$: $$ \begin{align*} \binom{p-\ell}k &= \frac{(p-\ell)(p-\ell-1)\cdots (p-\ell-k+1)}{k!}\\[.5em] & \equiv \frac{-\ell(-\ell-1)\cdots(-\ell-k+1)}{k!}\\[.5em] & \equiv (-1)^k\frac{\ell(\ell+1)\cdots (\ell+k-1)}{k!}\\[.5em] &\equiv (-1)^k\binom{\ell+k-1}k\\[.5em] &\equiv \binom{-\ell}k\pmod p. \end{align*}$$ Und noch einen dritten Beweis mit Potenzreihen in $\IF_p[[x]]$: $$\begin{align*} (1+x)^{p^m-\ell} &= (1+x)^{p^m}(1+x)^{-\ell} \\ &= (1+x^{p^m})\sum_{k\geq 0}\binom{-\ell}k x^k \\ &= \sum_{k= 0}^{p^m-\ell}\binom{-\ell}kx^k + \sum_{k= p^m-\ell+1}^{p^m-1}\binom{-\ell}k x^k + \sum_{k\geq p^m}\left(\binom{-\ell}k+ \binom{-\ell}{k-p^m}\right)x^k. \end{align*}$$
  • 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

Die Formel von Legendre

Wir wenden uns nun ab von der Frage nach dem Rest von $\binom nk$ modulo $p$ und fragen stattdessen nach der größten Potenz von $p$, die ein Teiler von $\binom nk$ ist. Hierzu definieren wir für $n\geq 1$ die $p$-adische Bewertung $\nu_p(n)$ von $n$ als die größte Zahl $m\in \IN$, für die $p^m$ ein Teiler von $ n$ ist. Äquivalent dazu ist, dass $\nu_p(n)$ der Exponent von $p$ in der Primfaktorzerlegung von $n$ ist. Man sieht leicht, dass für positive natürliche Zahlen $a,b\in \IN$ die Gleichung $\nu_p(ab) =\nu_p(a)+\nu_p(b)$ gilt. Bevor wir im nächsten Abschnitt $\nu_p(\binom nk)$ berechnen, werden wir eine effiziente Methode kennen lernen um $\nu_p(n!)$ zu berechnen. Wir benötigen noch zwei Definitionen:
  • 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$.
Formel von Legendre. Für $n\in \IN$ und $p$ prim gilt $$ \nu_p(n!) = \sum_{k=1}^\infty \left\lfloor \frac n{p^k}\right\rfloor =\frac{n-Q_p(n)}{p-1}.$$
Beweis: In $n!= 1\cdot 2\cdot \ldots \cdot n$ steuert jeder durch $p$ teilbare Faktor einen Faktor $p$ zur Primfaktorzerlegung von $n!$ bei, jeder durch $p^2$ teilbare Faktor einen weiteren, u.s.w. Da $\lfloor \frac n{p^k}\rfloor$ die Anzahl der durch $p^k$ teilbaren Faktoren ist, gilt $$ \nu_p(n!) = \sum_{k=1}^\infty \left\lfloor \frac n{p^k}\right\rfloor.$$ Sei $n=[n_m,\ldots, n_0]_p$ eine $p$-adische Darstellung von $n$. Dann ist $$ \begin{align*} \nu_p(n!) &= \sum_{k=1}^\infty \left\lfloor \frac {n_0+n_1p+\ldots n_mp^m}{p^k}\right\rfloor\\ &= \sum_{k=1}^m (n_k+n_{k+1}p+\ldots +n_mp^{m-k})\\ &= 0n_0 + 1n_1 + (p+1)n_2 +(p^2+p+1)n_3+\ldots + (p^{m-1}+p^{m-2}+\ldots +1)n_m\\ &= \frac{(p^0-1)n_0 +(p^1-1)n_1+(p^2-1)n_2+\ldots (p^m-1)n_m}{p-1}\\ &= \frac{(n_0+n_1p+\ldots n_mp^m) - (n_0+n_1+\ldots n_m)}{p-1}\\ &= \frac{n- Q_p(n)}{p-1}. \square \end{align*}$$

Ü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

Der Satz von Kummer

Bei der schriftlichen Addition und Subtraktion im $b$-adischen System kann es zu Überträgen kommen: \begin{array}{r} [1,9,0,9]_{10}\\ +[\mathclap{\underset 10},1,\mathclap{\underset 11},3]_{10}\\ \hline [2,0,2,2]_{10} \end{array} \qquad \begin{array}{r} [2,0,2,2]_{10}\\ -[\mathclap{\underset 10},1,\mathclap{\underset 11},3]_{10}\\ \hline [1,9,0,9]_{10} \end{array} Es ist unmittelbar klar, dass im $p$-adischen System bei der Berechnung der Differenz von $n$ und $k$ genauso viele Überträge stattfinden, wie bei der Berechnung der Summe von $k$ und $n-k$. Überraschenderweise hat die Anzahl dieser Überträge eine konkrete Bedeutung für die Teilbarkeit des Binomialkoeffizienten $\binom nk$ durch $p$.
Satz von Kummer. Für $0\leq k \leq n$ ist die Anzahl der Überträge bei der Addition von $k$ und $n-k$ im $p$-adischen System gleich $\nu_p(\binom nk)$.
Beweis: Es seien $n=[n_m,n_{m-1},\ldots, n_0]_p$, $k=[k_m,k_{m-1},\ldots, k_0]_p$ und $n-k = [\ell_m,\ell_{m-1},\ldots, \ell_0]_p$ die $p$-adischen Darstellungen von $n,k$ und $n-k$. Indem wir führende Nullen ergänzen, können wir o.B.d.A. annehmen, dass $k_m=\ell_m=0$ gilt. Es seien $u_1,u_2,\ldots, u_m\in\{0,1\}$ die Überträge bei Addition von $k$ und $n-k$: \begin{array}{rcccccl} [&k_m,&k_{m-1},&\ldots,&k_1, &k_0&]_p\\ +[&\mathclap{\underset{u_{m}}{\ell_{m}}}},&\mathclap{\underset{u_{m-1}}{\ell_{m-1}}}},&\ldots,&\mathclap{\underset{u_{1}}{\ell_{1}}}}, &\ell_0&]_p\\ \hline [&n_m,&n_{m-1},&\ldots,&n_1, &n_0&]_p \end{array} Wenn wir zusätzlich $u_0:=0$ und $u_{m+1}:=0$ festlegen, dann gilt $$ n_i = k_i+\ell_i+u_i-p(u_i+1)$$ für $i=0,\ldots, m$. Wegen $\binom nk = \frac{n!}{k!(n-k)!}$ folgt aus der Formel von Legendre, dass $$ \begin{align*} \nu_p\left(\binom nk\right) &= \frac {Q_p(k)+Q_p(n-k)- Q_p(n)}{p-1}\\ &= \frac 1{p-1}((k_0+\ldots+k_m) + (\ell_0+\ldots+\ell_m) - (n_0+\ldots+n_m))\\ &= \frac 1{p-1}((k_0+\ell_0-n_0) + \ldots + (k_m+\ell_m-n_m))\\ &= \frac 1{p-1}((pu_1-u_0) + (pu_2-u_1)+\ldots + (pu_{m+1}-u_m))\\ &= \frac 1{p-1}((p-1)(u_1+u_2+\ldots +u_m)-u_0 + pu_{m+1})\\ &= u_1+u_2+\ldots +u_m. \square \end{align*}$$

Ü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$ \begin{array}{r} [3,1,0,4,2]_5\\ -[\mathclap{\underset 11},{\underset12},1,{\underset13},3]_5\\ \hline [1,3,4,0,4]_5 \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
    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
    3. \showoff
    4. 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 \begin{array}{r} [1,\phantom{p-{}}0,0,\ldots,0]_p\\ -[\mathclap{\underset 10},\phantom{p-{}}1,0,\ldots,0]_p\\ \hline [0,p-1,0,\ldots,0]_p \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 \begin{array}{r} [n_m,n_{m-1},\ldots, n_j,\ldots, n_0]_p\\ -[n_m,n_{m-1},\ldots, 0_{\phantom{j}},\ldots, n_0]_p\\ \hline [ n_j,\ldots, \mathclap{0_{\phantom 0}}]_p \end{array} zeigt, dass $ \binom nk$ nicht durch $p$ teilbar ist. Also gilt $d=1$. \showoff
      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: \begin{array}{rcccccccccl} [&n_m\phantom{{}-1},&n_{m-1},&\ldots, &n_{r+1}, &n_r\phantom{{}+1}, &p-1, &p-1,&\ldots,& p-1&]_p\\ -[&\mathclap{\underset 1{n_m-1}},&\mathclap{\underset 1{n_{m-1}}},&\ldots ,&\mathclap{\underset 1{n_{r+1}}}, &n_r+1, &p-1, &p-1,&\ldots,& p-1&]_p\\ \hline [&0,&p-1,&\ldots, &p-1, &p-1, &0,&0,&\ldots, &0&]_p \end{array} 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

    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.
    \(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 419
 
Aufrufstatistik des Artikels
Insgesamt 6 externe Seitenaufrufe zwischen 2022.03 und 2022.05 [Anzeigen]
DomainAnzahlProz
https://matheplanet.de116.7%16.7 %
https://matheplanet.com116.7%16.7 %
https://duckduckgo.com233.3%33.3 %
https://google.de116.7%16.7 %
https://google.com116.7%16.7 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 1 Aufruf in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2022.05.14 20:07https://matheplanet.de/

[Top of page]

"Mathematik: Teilbarkeit von Binomialkoeffizienten durch Primzahlen und Primzahlpotenzen" | 4 Comments
The authors of the comments are responsible for the content.

Re: Teilbarkeit von Binomialkoeffizienten durch Primzahlen und Primzahlpotenzen
von: Slash am: Fr. 25. Februar 2022 20:05:11
\(\begingroup\)Ein wirklich gelungenes Debüt!\(\endgroup\)
 

Re: Teilbarkeit von Binomialkoeffizienten durch Primzahlen und Primzahlpotenzen
von: Wario am: Do. 10. März 2022 18:41:59
\(\begingroup\)Sauber und ordentlich strukturierter sowie geTeXter Artikel von interessantem Inhalt. \(\endgroup\)
 

Re: Teilbarkeit von Binomialkoeffizienten durch Primzahlen und Primzahlpotenzen
von: Wario am: Fr. 11. März 2022 13:38:13
\(\begingroup\)PS: Vielleicht übersehe ich etwas, aber wenn ich \mathclap weglasse sehe ich keinen Unterschied. Vielleicht ist also auch die $-Umgebung möglich. $ \begin{array}{r} [1,9,0,9]_{10}\\ +[\mathclap{\underset 10},1,\mathclap{\underset 11},3]_{10}\\ \hline [2,0,2,2]_{10} \end{array} \qquad \begin{array}{r} [2,0,2,2]_{10}\\ -[{\underset 10},1,\mathclap{\underset 11},3]_{10}\\ \hline [1,9,0,9]_{10} \end{array} $ $ \begin{array}{r} [1,9,0,9]_{10}\\ +[{\underset 10},1,{\underset 11},3]_{10}\\ \hline [2,0,2,2]_{10} \end{array} \qquad \begin{array}{r} [2,0,2,2]_{10}\\ -[{\underset 10},1,{\underset 11},3]_{10}\\ \hline [1,9,0,9]_{10} \end{array} $\(\endgroup\)
 

Re: Teilbarkeit von Binomialkoeffizienten durch Primzahlen und Primzahlpotenzen
von: Nuramon am: Fr. 11. März 2022 14:05:31
\(\begingroup\)@Wario: Ehrlich gesagt, bin ich mir nicht ganz sicher, ob man das \mathclap überall braucht. Irgendeine Formel sah ohne aber nicht besonders schick aus, und dann habe ich es vermutlich überall verwendet. Ohne \mathclap gibt es auf jeden Fall einen Unterschied zwischen \$-Umgebung und math-Tags, der sichtbar wird, wenn man Buchstaben statt Ziffern in der Summe hat: $$ \begin{array}{r} [x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x]_{10}\\ +[{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x}]_{10}\\ \hline [x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x]_{10} \end{array} $$ $ \begin{array}{r} [x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x]_{10}\\ +[{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x},{\underset 1x}]_{10}\\ \hline [x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x]_{10} \end{array} $ Interessanterweise sieht dieser Kommentar in der Vorschau des Forums (nicht hier im Kommentarbereich) auch anders aus als nach dem Absenden (in Brave/Chrome zumindest): In der Forumsvorschau ist die zweite Zeile in der \$-Umgebung minimal breiter als die erste, hier im Kommentarbereich sehe ich die zweite Zeile als kürzer als die erste. Mit math-Tags sieht alles gleich lang aus. Screenshot der Forumsvorschau: https://matheplanet.com/matheplanet/nuke/html/uploads/b/21445_Summe_in_Forumsvorschau.jpg Screenshot meines Kommentars unter diesem Artikel: https://matheplanet.com/matheplanet/nuke/html/uploads/b/21445_Summe_im_Kommentarbereich.jpg\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]