| |
| | Vorschau: |
| Eine Symmetrie im Pascalschen Dreieck |
\(\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}\)
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 - 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
- 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
|
|
|
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
