1 files changed, 553 insertions, 0 deletions
diff --git a/buch/chapters/30-endlichekoerper/galois.tex b/buch/chapters/30-endlichekoerper/galois.tex
index 5afef53..fbacba6 100644
--- a/buch/chapters/30-endlichekoerper/galois.tex
+++ b/buch/chapters/30-endlichekoerper/galois.tex
@@ -3,8 +3,561 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
+% !TeX spellcheck = de_CH
 \section{Galois-Körper
 \label{buch:section:galoiskoerper}}
 \rhead{Galois-Körper}
+Ein Körper $\Bbbk$ enthält mindestens die Zahlen $0$ und $1$.
+Die Null ist nötig, damit $\Bbbk$ eine Gruppe bezüglich der
+Addition ist, die immer ein neutrales Element, geschrieben $0$
+enthält.
+Die Eins ist nötig, damit $\Bbbk^*=\Bbbk\setminus\{0\}$ eine
+Gruppe bezüglich der Multiplikation ist, die immer eine neutrales
+Element, geschrieben $1$ enthält.
+Durch wiederholte Addition entstehen auch die Zahlen $2=1+1$, $3=2+1$ 
+und so weiter.
+Es sieht also so aus, als ob ein Körper immer unendliche viele
+Elemente enthalten müsste.
+Wie können also endliche Körper entstehen?
 
+In diesem Abschnitt sollen die sogenannten Galois-Körper $\mathbb{F}_p$
+mit genau $p$ Elementen konstruiert werden, die es für jede Primzahl $p$ gibt.
+Sie sind die Basis für weitere endliche Körper, die eine beliebige
+Primzahlpotenz $p^n$ von Elementen haben und die die Basis wichtiger
+kryptographischer Algorithmen sind.
 
+%
+% Arithmetik module $o$
+%
+\subsection{Arithmetik modulo $p$
+\label{buch:subsection:arithmetik-modulo-p}}
+Damit aus den Zahlen $0, 1, 2, \dots$ ein endlicher Körper werden kann,
+muss die Folge sich wiederholen.
+Schreiben wir $a_0=0,a_1=1,\dots$ für die Folge, dann muss es also
+ein Folgenelement $a_k$ geben und ein $n$ derart, dass $a_{k+n}=a_{k}$.
+Dies bedeutet, dass $k+n = k$ sein muss.
+Subtrahiert man $k$ auf beiden Seiten, dann folgt, dass $n=0$ sein muss.
+Damit ein endlicher Körper entsteht, muss also die Menge
+\begin{align*}
+&\{0,1,2,\dots,n-1\}
+\intertext{eine Gruppe bezüglich der Addition sein, und}
+&\{1,2,\dots,n-1\}
+\end{align*}
+eine Gruppe bezüglich der Multiplikation.
+
+\subsubsection{Restklassenring}
+Wir definieren die Grundoperationen in einer Menge, die mit den
+Zahlen $\{0,1,2,\dots,n-1\}$ identifiziert werden kann.
+
+\begin{definition}
+Die Zahlen $a,b\in\mathbb{Z}$ heissen {\em kongruent modulo $n$},
+geschrieben
+\[
+a\equiv b\mod n,
+\]
+wenn $a-b$ durch $n$ teilbar ist, also $n|(a-b)$.
+\end{definition}
+
+Die Zahlen mit gleichem Rest sind Äquivalenzklassen der Kongruenz modulo $n$.
+Die Zahlen mit Rest $k$ modulo $n$ bilden die {\em Restklasse}
+\[
+\llbracket k\rrbracket=\{\dots,k-2n,k-n,k,k+n,k+2n,\dots\} \subset\mathbb{Z}.
+\]
+Sie bilden eine endliche Menge, die man mit den Resten $0,1,\dots,n-1$
+identifizieren kann.
+
+\begin{definition}
+Die Menge $\mathbb{Z}/n\mathbb{Z}$ besteht aus den Restklassen
+$\llbracket 0\rrbracket,\llbracket 1\rrbracket,\dots,\llbracket n-1\rrbracket$,
+die auch einfach $0,1,\dots,n-1$ geschrieben werden.
+\end{definition}
+
+Beim Rechnen mit Resten modulo $n$ können Vielfache von $n$ ignoriert werden.
+Zum Beispiel gilt 
+\[
+\begin{aligned}
+48&\equiv -1\mod 7& 48&=-1&&\text{in $\mathbb{Z}/7\mathbb{Z}$}
+\\
+3\cdot 5=15&\equiv 1\mod 7 & 3\cdot 5&=1&&\text{in $\mathbb{Z}/7\mathbb{Z}$.}
+\end{aligned}
+\]
+Das Beispiel zeigt, dass man mindestens in $\mathbb{Z}/7\mathbb{Z}$ mit
+Resten ganz ähnlich rechnen kann wie in $\mathbb{Q}$.
+In $\mathbb{Z}/7\mathbb{Z}$ scheinen $3$ und $5$ multiplikative inverse
+zu sein.
+
+Tatsächlich kann man auf den Restklassen eine Ringstruktur definieren.
+Dazu muss man sicherstellen, dass die Auswahl eines Repräsentanten keinen
+Einfluss auf den Rest hat.
+Der Rest $a$ kann jede Zahl der Form $a+kn$ darstellen.
+Ebenso kann der Rest $b$ jede zahl der Form $b+ln$ darstellen.
+Deren Summe ist $a+b+(k+l)n\equiv a+b\mod n$.
+Der Repräsentant des Restes hat also keinen Einfluss auf die Summe.
+
+Ebenso ist das Produkt der beiden Repräsentaten 
+$(a+kn)\cdot(b+ln) = ab + (al+bk)n + kln^2=ab + (al+bk+kln)n\equiv ab\mod n$
+für jede Wahl von $k$ und $l$.
+Auch die Multiplikation ist also unabhängig vom gewählten Repräsentanten.
+
+\begin{definition}
+Die Menge $\mathbb{Z}/n\mathbb{Z}$ ist ein Ring,
+heisst der {\em Restklassenring modulo $n$}.
+\end{definition}
+
+\subsubsection{Division in $\mathbb{Z}/n\mathbb{Z}$}
+Um einen endlichen Körper zu erhalten, muss die Menge
+\[
+\mathbb{Z}/n\mathbb{Z} \setminus \{\llbracket0\rrbracket\}
+=
+\{
+\llbracket 1\rrbracket,
+\llbracket 2\rrbracket,
+\dots
+\llbracket n-q\rrbracket
+\}
+\]
+eine Gruppe bezüglich der Multiplikation sein.
+Insbesondere darf kein Produkt $a\cdot b$ mit Faktoren in 
+$\mathbb{Z}/n\mathbb{Z} \setminus \{\llbracket0\rrbracket\}$
+zu Null werden.
+Für $n=15$ funktioniert dies nicht, das Produkt $3\cdot 5\equiv 0\mod 15$.
+Man nennt von Null verschiedene Faktoren, deren Produkt Null ist, einen
+{\em Nullteiler}.
+Falls sich $n=p_1\cdot p_2$ in zwei Faktoren zerlegen lässt, dann sind
+$p_1$ und $p_2$ Nullteiler in $\mathbb{Z}/n\mathbb{Z}$.
+Ein Körper kann also nur entstehen, wenn $n$ eine Primzahl ist.
+
+\begin{definition}
+Ist $p$ eine Primzahl, dann heisst $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$
+der Galois-Körper der Ordnung $p$.
+\end{definition}
+
+Diese Definition ist nur gerechtfertigt, wenn $\mathbb{F}_p^*$ tatsächlich
+eine Gruppe ist, wenn also jede Zahl zwischen $1$ und $p-1$ ein Inverses
+bezüglich der Multiplikation hat.
+Zu einem Rest $a\in\mathbb{F}_p^*$ muss also ein Rest $b$ gefunden werden,
+so dass $ab\equiv 1\mod p$.
+Dies ist gleichbedeutend mit Zahlen $b$ und $n$ derart, dass
+\begin{equation}
+ab+np=1.
+\label{buch:endliche-koerper:teilerfremd}
+\end{equation}
+In~\eqref{buch:endliche-koerper:teilerfremd} sind $a$ und $p$ gegeben,
+gesucht sind $b$ und $n$.
+
+In Abschnitt~\ref{buch:section:euklid} wurde gezeigt, wie der euklidische
+Algorithmus eine Gleichung der Form~\eqref{buch:endliche-koerper:teilerfremd}
+lösen kann, wenn die beiden gegebenen Zahlen $a$ und $p$ teilerfremd sind.
+Dies ist aber dadurch garantiert, dass $p$ eine Primzahl ist und $1\le a <p$.
+Die multiplikative Inverse von $a$ in $\mathbb{F}_p^*$ kann also mit
+Hilfe des euklidischen Algorithmus effizient gefunden werden.
+
+\begin{beispiel}
+Die kleinste Primzahl grösser als $2021$ ist $p=2063$.
+Was ist die Inverse von $2021$ in $\mathbb{F}_{2063}$?
+
+Wir führen den euklidischen Algorithmus für das Paar $(2063,2021)$ durch
+und erhalten 
+\begin{center}
+\begin{tabular}{|>{$}c<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
+\hline
+k&  a_k&  b_k& q_k& r_k\\
+\hline
+0& 2063& 2021&   1&  42\\
+1& 2021&   42&  48&   5\\
+2&   42&    5&   8&   2\\
+3&    5&    2&   2&   1\\
+4&    2&    1&   2&   0\\
+\hline
+\end{tabular}
+\end{center}
+Die gesuchten Faktoren $b$ und $n$ können aus dem Matrizenprodukt
+$Q(q_n)\dots Q(q_0)$ gefunden werden:
+\begin{align*}
+Q
+&=
+\begin{pmatrix} 0& 1\\ 1& -2 \end{pmatrix}
+\begin{pmatrix} 0& 1\\ 1& -2 \end{pmatrix}
+\begin{pmatrix} 0& 1\\ 1& -8 \end{pmatrix}
+\begin{pmatrix} 0& 1\\ 1& -48 \end{pmatrix}
+\begin{pmatrix} 0& 1\\ 1& -1 \end{pmatrix}
+\\
+&=
+\begin{pmatrix} 0& 1\\ 1& -2 \end{pmatrix}
+\begin{pmatrix} 0& 1\\ 1& -2 \end{pmatrix}
+\begin{pmatrix} 0& 1\\ 1& -8 \end{pmatrix}
+\begin{pmatrix} 1& -1\\ -48& 49\end{pmatrix}
+\\
+&=
+\begin{pmatrix} 0& 1\\ 1& -2 \end{pmatrix}
+\begin{pmatrix} 0& 1\\ 1& -2 \end{pmatrix}
+\begin{pmatrix} -48& 49\\ 385& -393 \end{pmatrix}
+\\
+&=
+\begin{pmatrix} 0& 1\\ 1& -2 \end{pmatrix}
+\begin{pmatrix} 385& -393\\ -818& 835 \end{pmatrix}
+\\
+&=
+\begin{pmatrix} -818&   835\\ 2021& -2063\end{pmatrix}
+\end{align*}
+Daraus können wir ablesen, dass
+\[
+-818\cdot 2021 +835 \cdot 2063=1.
+\]
+Der Rest $ -818\equiv 1245\mod 2063$ ist also die multiplikative
+Inverse von $2021$ in $\mathbb{F}_{2063}$.
+\end{beispiel}
+
+\subsubsection{Der kleine Satz von Fermat}
+In $\mathbb{Z}$ wachsen die Potenzen einer Zahl immer weiter an.
+In einem endlichen Körper kann dies nicht gelten, da nur endlich
+viele Werte zur Verfügung stehen.
+Tatsächlich müssen die Potenzen einer von $0$ verschiedenen Zahl
+$a\in\mathbb{F}_p^*$ alle in $\mathbb{F}_p^*$ liegen.
+Es gibt aber nur $p-1$ Zahlen in $\mathbb{F}_p^*$, spätestens
+die Potenz mit Exponent $p$ muss also mit einer früheren Potenz
+übereinstimmen.
+Der kleine Satz von Fermat sagt etwas genauer: die $p$-te Potenz
+von $a$ ist genau die Zahl $a$:
+
+\begin{satz}[Kleiner Satz von Fermat]
+\label{buch:endliche-koerper:satz:fermat}
+In $\mathbb{F}_p$ gilt $a^p=a$ für alle $a\in\mathbb{F}_p^*$.
+\end{satz}
+
+Wir beweisen diesen Satz in der folgenden, traditionelleren 
+Formulierung.
+
+\begin{satz}
+Für jede ganze Zahl $a>0$ gilt $p|(a^p-a)$ genau dann, wenn
+$p$ eine Primzahl ist.
+\end{satz}
+
+\begin{proof}[Beweis]
+Wir müssen zeigen, dass $p$ ein Teiler ist von $a^p-a$.
+Das nachfolgende kombinatorische Argument wird zum Beispiel
+von Mathologor auf seinem Youtube-Kanal im Video
+\url{https://youtu.be/_9fbBSxhkuA} illustriert.
+
+Zum Beiweis interpretieren wir die vorkommenden Zahlen kombinatorisch.
+Die Zahl $a^p$ ist die Anzahl der verschiedenen Perlenketten der Länge
+$p$, die sich aus Glasperlen mit $a$ verschiedenen Farben herstellen
+lassen.
+Davon bestehen $a$ Perlenketten aus nur einer einzigen Farbe.
+Die Zahl $a^p-a$ ist also die Anzahl der Perlenketten der Länge $p$
+aus Glasperlen mit $a$ verschiedenen Farben, die mindestens zwei
+verschiedene Farben verwenden.
+
+Wir stellen jetzt die Frage nach der Anzahl der geschlossenen
+Perlenketten der Länge $p$ als Glasperlen in $a$ verschiedenen Farben.
+Aus jeder geschlossenen Perlenkette lassen sich $p$ Perlenketten machen,
+indem man sie an einer der $p$ Trennstellen zwischen Perlen aufteilt.
+
+Wir müssen uns noch überlegen, unter welchen Voraussetzungen 
+alle diese möglichen Auftrennungen zu verschiedenen Perlenketten
+führen.
+Zwei Trennstellen, die $k$-Perlen auseinander liegen, führen nur dann
+zur gleichen Perlenkette, wenn die geschlossenen Ketten durch Drehung 
+um $k$ Perlen ineinander übergehen.
+Dies bedeutet aber auch, dass sich das Farbmuster alle $k$-Perlen
+wiederholen muss.
+Folglich ist $k$ ein Teiler von $p$.
+$p$ verschiedene Perlenketten entstehen also immer genau dann, wenn $p$
+eine Primzahl ist.
+
+Wir schliessen daraus, dass $a^p-a$ durch $p$ teilbar ist, genau dann,
+wenn $p$ eine Primzahl ist.
+\end{proof}
+
+Der kleine Satz von Fermat kann auch dazu verwendet werden, Potenzen 
+in $\mathbb{F}_p$ zu vereinfachen, wie das folgende Beispiel\footnote{%
+Das Beispiel stammt aus dem Video~\url{https://youtu.be/_9fbBSxhkuA},
+welches Mathologer zu Halloween 2018 veröffentlich hat}
+zeigt.
+
+\begin{beispiel}
+Man berechnet in $\mathbb{F}_{13}$ die Potenz $11^{666}$.
+Nach dem kleinen Satz von Fermat ist $11^{13} = 11$ oder $11^{12}=1$,
+man kann also den Exponenten modulo $12$ reduzieren.
+Weil $666=55\cdot 12 + 6$ erhält man $11^{666}= 11^6$.
+Da die Potenzen von $11$ etwas mühsam zu berechnen sind,
+kann man sie wegen $11=-2$ in $\mathbb{F}_{13}$ auch als Potenzen
+von $-2$ bekommen.
+Aber $(-2)^6 = 64 = -1 \in\mathbb{F}_{13}$.
+\end{beispiel}
+
+In der Form $a^{p-1}=1$ in $\mathbb{F}_p$ liefert der kleine Satz
+von Fermat die Inverse von $a$ als $a^{p-2}$.
+Dies bedeutet zum Beispiel, dass in $\mathbb{F}_3$ jede von $0$
+verschiedene Zahl zu sich selbst invers ist: $1\cdot 1=1$ und $2\cdot 2=1$.
+Diese Art, die Inverse zu bestimmen, ist allerdings nicht effizienter
+als der euklidische Algorithmus, aber sie ist manchmal für
+theoretische Überlegungen nützlich.
+
+\subsubsection{Der Satz von Wilson}
+Der Satz von Wilson ermöglicht, die multiplikative Inverse auf eine
+andere Art zu berechnen.
+Sie ist zwar nicht unbedingt einfacher, aber manchmal nützlich für
+theoretische Überlegungen.
+
+\begin{satz}[Wilson]
+Die ganze Zahl $p\ge 2$ ist genau dann eine Primzahl, wenn
+$(p-1)!\equiv -1\mod p$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Wenn $p$ keine Primzahl ist, dann lässt sich $p$ in Faktoren
+$p=n_1\cdot n_2=p$ zerlegen.
+Beide Faktoren kommen in der Liste $1,2,\dots,p-1$ vor.
+Insbesondere haben $p=n_1n_2$ und $(p-1)!$ mindestens einen
+der Faktoren $n_1$ oder $n_2$ gemeinsam, wir können annehmen,
+dass $n_1$ dieser Faktor ist.
+Es folgt, dass der grösste gemeinsame Teiler von $p$ und $(p-1)!$
+grösser als $n_1$ ist, auch $(p-1)!$ ein Vielfaches von $n_1$ in
+$\mathbb{F}_p$.
+Insbesondere kann $(p-1)!$ nicht $-1\in\mathbb{F}_p$ sein.
+
+Ist andererseits $p$ eine Primzahl, dann sind die Zahlen $1, 2,\dots,p-1$
+alle invertierbar in $\mathbb{F}_p$.
+Die Zahlen $1$ und $-1\equiv p-1\mod p$ sind zu sich selbst invers,
+da $1\cdot 1=1$ und $(-1)\cdot(-1)=1$.
+Wenn eine Zahl $a$ zu sich selbst invers ist in $\mathbb{F}_p$,
+dann ist $a^2-1=0$ in $\mathbb{F}_p$.
+Daher ist auch $(a+1)(a-1)=0$, in $\mathbb{F}_p$ muss daher einer
+der Faktoren $0$ sein, also $a=-1$ oder $a=1$ in $\mathbb{F}_p$.
+
+Zu jeder Zahl $a\in\{2,\dots,p-2\}$ liegt die Inverse $a^{-1}$
+ebenfalls in diesen Bereich und ist verschieden von $a$: $a^{-1}\ne a$.
+Das Produkt der Zahlen
+$2\cdot 3 \cdot\ldots\cdot (p-2)$ besteht also aus zueinander inversen
+Paaren.
+Es folgt
+\[
+2\cdot 3 \cdot\ldots\cdot (p-2) = 1.
+\]
+Multipliziert man dies mit $p-1=-1\in\mathbb{F}_p$, folgt
+die Behauptung des Satzes.
+\end{proof}
+
+Mit dem Satz von Wilson kann man die Inverse einer beliebigen Zahl
+$a\in\mathbb{F}_p$ finden.
+Dazu verwendet man, dass $a$ einer der Faktoren in $(p-1)!$ ist.
+Lässt man diesen Faktor weg, erhält man eine Zahl
+\[
+b = 1\cdot 2 \cdot \ldots\cdot \hat{a}\cdot\ldots\cdot (p-1),
+\]
+wobei der Hut bedeutet, dass der Faktor $a$ weggelassen werden soll.
+Nach dem Satz von Wilson ist $ab=-1$ in $\mathbb{F}_p$, also ist
+$-b$ die multiplikative Inverse  von $a$.
+
+\begin{beispiel}
+Die Inverse von $2\in\mathbb{F}_7$ ist
+\begin{align*}
+a^{-1}
+&=
+-\underbrace{1\cdot 3\cdot 4}_{}\cdot \underbrace{5\cdot 6}_{}
+\\
+&=
+-5\cdot 2
+=
+-3
+=4
+\end{align*}
+Tatsächlich ist $2\cdot 4=8\equiv 1\mod 7$.
+\end{beispiel}
+
+%
+% Charakteristik
+%
+\subsection{Charakteristik
+\label{buch:subsection:charakteristik}}
+In diesem Abschnitt zeigen wir, dass jeder Körper $\Bbbk$ eine Erweiterung
+entweder von $\mathbb{Q}$ oder eines endlichen Körpers $\mathbb{F}_p$ ist.
+
+\subsubsection{Primkörper}
+Sei $\Bbbk$ ein Körper.
+Er enthält mindestens die Zahlen $0$ und $1$ und alle Vielfachen davon.
+Wenn alle Vielfachen in $\Bbbk$ von $0$ verschieden sind, dann
+bilden Sie ein Bild der ganzen Zahlen $\mathbb{Z}\subset\Bbbk$.
+Damit müssen dann aber auch alle Brüche in $\Bbbk$ enhalten sein,
+es folgt also, dass $\mathbb{Q}\subset\Bbbk$ sein muss.
+
+Wenn andererseits eines der Vielfachen von $1$ in $\Bbbk$ 
+verschwindet, dann wissen wir aus
+Abschnitt~\ref{buch:subsection:arithmetik-modulo-p}, dass
+der Körper $\mathbb{F}_p$ in $\Bbbk$ enthalten sein muss.
+Dies ist der kleinste Teilkörper, der in $\Bbbk$ enthalten ist.
+
+\begin{definition}
+Der kleinste Teilkörper eines Körpers $\Bbbk$ heisst der 
+{\em Primkörper} von $\Bbbk$.
+\end{definition}
+
+Der Primkörper erlaubt jetzt, die Charakteristik eines Körpers $\Bbbk$
+zu definieren.
+
+\begin{definition}
+Die Charakteristik eines Körpers $\Bbbk$ ist $p$, wenn der Primkörper
+$\mathbb{F}_p$ ist.
+Falls der Primkörper $\mathbb{Q}$ ist, ist die Charakteristik $0$.
+\end{definition}
+
+Die Charakteristik hat wichtige Auswirkungen darauf, wie in einem Körper
+gerechnet wird.
+Endliche Körper enthalten immer einen Körper von Primzahl-Ordnung und
+haben damit immer Primcharakteristik.
+Ein Körper mit Charakteristik $0$ enthält immer unendliche viele
+Elemente.
+
+\subsubsection{Teilbarkeit von Binomialkoeffizienten}
+\begin{figure}
+\centering
+\includegraphics{chapters/30-endlichekoerper/images/binomial2.pdf}
+\caption{Binomialkoeffizienten module $2$ im Pascal-Dreieck.
+Auf den rot hinterlegten Zeilen, die zu Exponenten der Form $2^k$ gehören,
+sind alle Koeffizienten ausser dem ersten und letzten durch $2$ teilbar.
+\label{buch:endliche-koerper:fig:binomial2}}
+\end{figure}
+\bgroup
+\input{chapters/30-endlichekoerper/images/farben.tex}
+\begin{figure}
+\centering
+\includegraphics{chapters/30-endlichekoerper/images/binomial5.pdf}
+\caption{Binomialkoeffizienten module $5$ im Pascal-Dreieck.
+Die von $0$ verschiedenen Reste werden durch Farben dargestellt:
+$1=\text{schwarz}$,
+$2=\text{\color{farbe2}rot}$,
+$3=\text{\color{farbe3}grün}$,
+$4=\text{\color{farbe4}blau}$.
+Auf den gelb hinterlegten Zeilen, die zu Exponenten der Form $5^k$ gehören,
+sind alle Koeffizienten ausser dem ersten und letzten durch $5$ teilbar.
+\label{buch:endliche-koerper:fig:binomial5}}
+\end{figure}
+\egroup
+Die Abbildung~\ref{buch:endliche-koerper:fig:binomial2} zeigt den
+Rest bei Teilung durch $2$ der Binomialkoeffizienten.
+Man kann daraus ablesen, dass $\binom{n}{m}\equiv 0\mod 2$ für $n=2^k$ 
+und $0<m<n$.
+Abbildung~\ref{buch:endliche-koerper:fig:binomial5} zeigt das Pascal-Dreieck
+auch noch für $p=5$.
+Hier ist auch schön die Selbstähnlichkeit des Pascal-Dreiecks erkennbar.
+Ersetzt man die ``5er-Dreiecke'' durch ein volles Dreieck mit der Farbe
+des kleinen Dreiecks an seiner Spitze, entsteht wieder das ursprüngliche
+Pascal-Dreieck.
+Dabei gehen die Zeilen aus lauter Nullen ausser an den Enden ineinander über.
+
+\begin{satz}
+\label{buch:endliche-koerper:satz:binom}
+Sei $p$ eine Primzahl, dann ist
+\[
+\binom{p}{m} \equiv 0\mod p
+\]
+für $0<m<n$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Für den Binomialkoeffizienten gilt
+\[
+\binom{p}{m}
+=
+\frac{p\cdot (p-1)\cdot(p-2)\cdot\ldots\cdot (p-m+1)}{1\cdot 2\cdot 3\cdot\ldots\cdot m}.
+\]
+Für $m<p$ kann keiner der Faktoren im Nenner $p$ sein, der Faktor $p$
+im Zähler kann also nicht weggekürzt werden, so dass der Binomialkoeffizient
+durch $p$ teilbar sein muss.
+\end{proof}
+
+\begin{satz}
+\label{buch:endliche-koerper:satz:binomk}
+Sei $p$ eine Primzahl, dann ist
+\begin{equation}
+\binom{p^k}{m} \equiv 0\mod p
+\label{buch:endliche-koerper:eqn:a+b^p^k}
+\end{equation}
+für $0<m<p^k$
+\end{satz}
+
+\begin{proof}[Beweis]
+Wir wissen aus Satz \ref{buch:endliche-koerper:satz:binom}, dass 
+\begin{equation}
+(a+b)^p = a^p+b^p.
+\label{buch:endliche-koerper:eqn:a+b^p}
+\end{equation}
+Wir müssen zeigen, dass $(a+b)^{p^k}=a^{p^k}+b^{p^k}$ gilt.
+Wir verwenden vollständige Induktion, 
+\eqref{buch:endliche-koerper:eqn:a+b^p} ist die Induktionsverankerung.
+Wir nehmen jetzt im Sinne der Induktionsannahme an, dass
+\eqref{buch:endliche-koerper:eqn:a+b^p^k} für ein bestimmtes $k$ gilt.
+Dann ist
+\[
+(a+b)^{p^{k+1}}
+=
+(a+b)^{p^k\cdot p}
+=
+\bigl((a+b)^{p^k}\bigr)^p
+=
+(a^{p^k}+b^{p^k})^p
+=
+a^{p^k\cdot p}+b^{p^k\cdot p}
+=
+a^{p^{k+1}}
++
+b^{p^{k+1}},
+\]
+also die Behauptung für $k+1$.
+Damit ist
+\eqref{buch:endliche-koerper:eqn:a+b^p^k} für alle $k$ bewiesen.
+\end{proof}
+
+Die Aussage von Satz~\ref{buch:endliche-koerper:satz:binomk} kann man 
+auch im Körper $\mathbb{F}_p$ formulieren:
+
+\begin{satz}
+\label{buch:endliche-koerper:satz:binomFp}
+In $\mathbb{F}_p$ gilt
+\[
+\binom{p^k}{m}=0
+\]
+für beliebige $k>0$ und $0<m<p^k$.
+\end{satz}
+
+\subsubsection{Frobenius-Automorphismus}
+Die Abbildung $x\mapsto x^n$ ist weit davon entfernt, sich mit den
+algebraischen Strukturen zu vertragen.
+Zum Beispiel kann man nicht erwarten, dass $(a+b)^n = a^n + b^n$,
+denn nach der binomischen Formel
+\begin{equation}
+(a+b)^n
+=
+\sum_{k=0}^n \binom{n}{k} a^k b^{n-k}
+=
+a^n + \binom{n}{1}a^{n-1}b + \dots + \binom{n}{n-1}ab^{n-1} + b^n
+\label{buch:endliche-koerper:fig:binomischeformel}
+\end{equation}
+gibt es zwischen den Termen an den Enden des Ausdrucks noch viele
+Zwischenterme, die normalerweise nicht verschwinden.
+
+Ganz anders sieht die Situation aus, wenn $n=p$ ist.
+Nach Satz~\ref{buch:endliche-koerper:satz:binomFp} verschwinden die
+Binomialkoeffizienten der Zwischenterme der Summe
+\eqref{buch:endliche-koerper:fig:binomischeformel}
+als Elemente von $\mathbb{F}_p$.
+Daher gilt
+
+\begin{satz}[Frobenius-Automorphismus]
+In einem Körper $\Bbbk$ der Charakteristik $p$ ist die Abbildung
+$x\mapsto x^p$ ist ein Automorphismus, der den Primkörper 
+$\mathbb{F}_p\subset\Bbbk$ fest lässt.
+\end{satz}
+
+\begin{proof}[Beweis]
+Wir müssen uns nur noch davon überzeugen, dass $\mathbb{F}_p\subset\Bbbk$
+fest bleibt.
+Nach dem kleine Satz von Fermat~\ref{buch:endliche-koerper:satz:fermat}
+ist $a^p=a$ für alle $a\in\mathbb{F}_p$, der Frobenius-Automorphismus
+lässt also alle Elemente von $\mathbb{F}_p$ fest.
+\end{proof}
+
+\begin{definition}
+Der Automorphismus $x\mapsto x^p$ heisst {\em Frobenius-Automorphismus}.
+\end{definition}