Merge remote-tracking branch 'upstream/master' into mceliece

7 files changed, 345 insertions, 72 deletions

diff --git a/buch/chapters/30-endlichekoerper/chapter.tex b/buch/chapters/30-endlichekoerper/chapter.tex
index 1a0a323..b4c602e 100644
--- a/buch/chapters/30-endlichekoerper/chapter.tex
+++ b/buch/chapters/30-endlichekoerper/chapter.tex
@@ -8,13 +8,14 @@
 \lhead{Endliche Körper}
 \rhead{}
 Aus den ganzen Zahlen $\mathbb{Z}$ entsteht ein Körper, indem wir Brüche
-bilden alle von $0$ verschiedenen Nenner zulassen.
+bilden und dabei alle von $0$ verschiedenen Nenner zulassen.
 Der Körper der rationalen Zahlen $\mathbb{Q}$ enthält unendliche
 viele Zahlen und hat zusätzlich die sogenannte archimedische Eigenschaft,
 nämliche dass es zu zwei positiven rationalen Zahlen $a$ und $b$ immer eine
 ganze Zahl $n$ gibt derart, dass $na>b$.
 Dies bedeutet auch, dass es in den rationalen Zahlen beliebig grosse Zahlen
 gibt.
+
 Man kann aus den ganzen Zahlen aber auch eine Reihe von Körpern ableiten,
 die diese Eigenschaft nicht haben.
 Nicht überraschend werden die ersten derartigen Körper, die wir
diff --git a/buch/chapters/30-endlichekoerper/euklid.tex b/buch/chapters/30-endlichekoerper/euklid.tex
index 0bf3016..a75046f 100644
--- a/buch/chapters/30-endlichekoerper/euklid.tex
+++ b/buch/chapters/30-endlichekoerper/euklid.tex
@@ -8,18 +8,33 @@
 \rhead{Der euklidische Algorithmus}
 Der euklidische Algorithmus bestimmt zu zwei gegebenen ganzen
 Zahlen $a$ und $b$ den grössten gemeinsamen Teiler $g$.
-Zusätzlich findet er ganze Zahlen $s$ und $t$ derart, dass
+
+\begin{definition}
+\label{buch:endliche-koerper:def:ggt}
+Der grösste gemeinsame Teiler von $a$ und $b$ ist die grösste
+ganze Zahl $g$, die sowohl $a$ als auch $b$ teilt: $g|a$ und
+$g|b$.
+\index{grösster gemeinsamer Teiler}%
+\index{ggT}%
+\end{definition}
+
+Zusätzlich findet der euklidische Algorithmus  ganze Zahlen $s$
+\index{euklidischer Algorithmus}%
+und $t$ derart, dass
 \[
 sa + tb = g.
 \]
 In diesem Abschnitt soll der Algorithmus zunächst für ganze Zahlen
 vorgestellt werden, bevor er auf Polynome verallgemeinert und dann
 in Matrixform niedergeschrieben wird.
+Die Matrixform ermöglicht, einfach zu implementierende iterative
+Algorithmen für die Zahlen $s$ und $t$ un später auch für die
+Berechnung des kleinsten gemeinsamen Vielfachen zu finden.
 
 %
 % Der euklidische Algorithmus für ganze Zahlen
 %
-\subsection{Ganze Zahlen}
+\subsection{Grösster gemeinsamer Teiler ganzer Zahlen}
 Gegeben sind zwei ganze Zahlen $a$ und $b$ und wir dürfen annehmen,
 dass $a\ge b$.
 Gesucht ist der grösste gemeinsame Teiler $g$ von $a$ und $b$.
@@ -55,11 +70,11 @@ neuen Quotienten $q_1$ und einen neuen Rest $r_1$ liefert mit $a_1-q_1b_1=r_1$.
 So entstehen vier Folgen von Zahlen $a_k$, $b_k$, $q_k$ und $r_k$ derart,
 dass in jedem Schritt gilt
 \begin{align*}
-a_k - q_kb_k &= r_k & g&|a_k & g&|b_k & a_k &= b_{k-1} & b_k = r_{k-1}
+a_k - q_kb_k &= r_k & g&|a_k & g&|b_k & a_k &= b_{k-1} & b_k = r_{k-1}.
 \end{align*}
 Der Algorithmus bricht im Schritt $n$ ab, wenn $r_{n+1}=0$.
 Der letzte nicht verschwindende Rest $r_n$ muss daher der grösste gemeinsame
-Teiler sein: $g=r_n$.
+Teiler $g$ von $a$ und $b$ sein: $g=r_n$.
 
 \begin{beispiel}
 \label{buch:endlichekoerper:beispiel1}
@@ -131,7 +146,7 @@ In jedem Schritt arbeitet man mit zwei ganzen Zahlen $a_k$ und $b_k$, die wir
 als zweidimensionalen Spaltenvektor betrachten können.
 Der Algorithmus macht aus $a_k$ und $b_k$ die neuen Zahlen
 $a_{k+1} = b_k$ und $b_{k+1} = r_k = a_k - q_kb_k$, dies
-kann man als
+kann man als die Matrixoperation
 \[
 \begin{pmatrix} a_{k+1} \\ b_{k+1} \end{pmatrix}
 =
@@ -143,7 +158,7 @@ kann man als
 schreiben.
 Der Algorithmus bricht ab, wenn die zweite Komponente des Vektors $=0$ ist,
 in der ersten steht dann der grösste gemeinsame Teiler.
-Hier ist die Durchführung des Algorithmus in Matrix-Schreibweise:
+Hier die Durchführung des Algorithmus in Matrix-Schreibweise:
 \begin{align*}
 \begin{pmatrix} 23205 \\ 6800 \end{pmatrix}
 &=
@@ -196,16 +211,16 @@ beschreiben.
 
 \begin{algorithmus}[Euklid]
 \label{lifting:euklid}
-Der Algorithmus operiert auf zweidimensionalen Zustandsvektoren
+Der Algorithmus operiert auf zweidimensionalen Vektoren
 $x\in\mathbb Z^2$ 
 wie folgt:
 \begin{enumerate}
-\item Initialisiere  den Zustandsvektor mit den ganzen Zahlen $a$ und $b$:
-$\displaystyle x = \begin{pmatrix}a\\b\end{pmatrix}$
+\item Initialisiere  den Vektor mit den ganzen Zahlen $a$ und $b$:
+$\displaystyle x = \begin{pmatrix}x_1\\x_2\end{pmatrix}=\begin{pmatrix}a\\b\end{pmatrix}$
 \item Bestimme den Quotienten $q$ als die grösste ganze Zahl,
 für die $qx_2\le x_1$ gilt.
-\item Berechne den neuen Zustandsvektor als $Q(q)x$.
-\item Wiederhole Schritte 2 und 3 bis die zweite Komponente des Zustandsvektors
+\item Berechne den neuen Vektor als $Q(q)x$.
+\item Wiederhole Schritte 2 und 3 bis die zweite Komponente des Vektors
 verschwindet.
 Die erste Komponente ist dann der gesuchte grösste gemeinsame Teiler.
 \end{enumerate}
@@ -319,13 +334,11 @@ Q(q) = \begin{pmatrix} 0 & 1 \\ 1 & -q \end{pmatrix}
 \]
 lässt sich mit genau einer Multiplikation und einer Addition
 berechnen.
-Dies ist die Art von Matrix, die wir für die Implementation der
-Wavelet-Transformation anstreben.
 
 %
 % Vereinfachte Durchführung des euklidischen Algorithmus
 %
-\subsection{Vereinfachte Durchführung
+\subsection{Iterative Durchführung des erweiterten euklidischen Algorithmus
 \label{buch:endlichekoerper:subsection:matrixschreibweise}}
 Die Durchführung des euklidischen Algorithmus mit Hilfe der Matrizen
 $Q(q_k)$ ist etwas unhandlich.
@@ -334,7 +347,7 @@ dargestellt werden, die leichter als Programm zu implementieren ist.
 
 In Abschnitt~\ref{buch:endlichekoerper:subsection:matrixschreibweise}
 wurde gezeigt, dass das Produkt der aus den Quotienten $q_k$ gebildeten
-Matrizen $Q(q_k)$ berechnet werden müssen.
+Matrizen $Q(q_k)$ berechnet werden muss.
 Dazu beachten wir zunächst, dass die Multiplikation mit der Matrix
 $Q(q_k)$ die zweite Zeile in die erste Zeile verschiebt:
 \[
@@ -357,7 +370,7 @@ u-q_kc&v-q_kd
 \]
 Die Matrizen
 \[
-Q_k = Q(q_k)Q(q_{k-1})\dots Q(q_0)
+Q_k = Q(q_k)Q(q_{k-1})\cdots Q(q_0)
 \]
 haben daher jeweils für aufeinanderfolgende Werte vo $k$ eine Zeile
 gemeinsam.
@@ -419,7 +432,7 @@ gesetzt werden muss.
 
 Mit diesen Notationen kann man den Algorithmus jetzt in der früher
 verwendeten Tabelle durchführen, die man um die zwei
-Spalten $c_k$ und $d_k$ hinzufügt und die Werte in dieser
+Spalten $c_k$ und $d_k$ erweitert und die Werte in dieser
 Spalte mit Hilfe der
 Rekursionsformeln~\eqref{buch:endlichekoerper:eqn:cdrekursion}
 aus den initialen Werten~\eqref{buch:endlichekoerper:eqn:cdinitial}
@@ -428,7 +441,7 @@ berechnet.
 \begin{beispiel}
 Wir erweitern das Beispiel von Seite~\pageref{buch:endlichekoerper:beispiel1}
 zur Bestimmung des grössten gemeinsamen Teilers von $76415$ und $23205$
-zur Berechnung der Koeffizienten $c_k$ und $d_k$
+um die Spalten zur Berechnung der Koeffizienten $c_k$ und $d_k$
 Wir schreiben die gefundenen Zahlen in eine Tabelle:
 \begin{center}
 \label{buch:endlichekoerper:beispiel1erweitert}
@@ -503,7 +516,7 @@ Tabelle vertauscht wurden.
 %
 % Der euklidische Algorithmus für Polynome
 %
-\subsection{Polynome}
+\subsection{Grösster gemeinsare Teiler von Polynomen}
 Der Ring $\mathbb{Q}[X]$ der Polynome in der Variablen $X$ mit rationalen
 Koeffizienten\footnote{Es kann auch ein beliebiger anderer Körper für
 die Koeffizienten verwendet werden.
@@ -579,7 +592,7 @@ ta+sb
 (X^4+X^3-7X^2-X+6)
 \\
 &=
--4X^2+4X+8
+-4X^2+4X+8,
 \end{align*}
 und dies ist tatsächlich der gefundene grösste gemeinsame Teiler.
 Die zweite Zeile von $Q$ gibt uns die Polynomfaktoren, mit denen
@@ -621,6 +634,8 @@ $ua-vb = ab/g - ab/g = 0$, wie erwartet.
 %
 \subsection{Das kleinste gemeinsame Vielfache
 \label{buch:subsection:daskgv}}
+\index{kleinstes gemeinsames Vielfaches}%
+\index{kgV}%
 Das kleinste gemeinsame Vielfache zweier Zahlen $a$ und $b$ ist
 \[
 \operatorname{kgV}(a,b)
@@ -631,8 +646,8 @@ Wir suchen nach einen Algorithmus, mit dem man das kleinste gemeinsame
 Vielfache effizient berechnen kann.
 
 Die Zahlen $a$ und $b$ sind beide Vielfache des grössten gemeinsamen
-Teilers $g=\operatorname{ggT}(a,b)$, es gibt also Zahlen $u$ und $v$ derart,
-dass $a=ug$ und $b=vg$.
+Teilers $g=\operatorname{ggT}(a,b)$.
+Es gibt daher Zahlen $u$ und $v$ derart, dass $a=ug$ und $b=vg$.
 Wenn $t$ ein gemeinsamer Teiler von $u$ und $v$ ist, dann ist $tg$ ein
 grösserer gemeinsamer Teiler von $a$ und $b$.
 Dies kann nicht sein, also müssen $u$ und $v$ teilerfremd sein.
@@ -641,6 +656,7 @@ Die Bestimmung des kleinsten gemeinsamen Vielfachen ist also gleichbedeutend
 mit der Bestimmung der Zahlen $u$ und $v$.
 
 Die definierende Eigenschaften von $u$ und $v$ kann man in Matrixform als
+\index{Matrixform des kgV-Algorithmus}%
 \begin{equation}
 \begin{pmatrix}
 a\\b
@@ -669,7 +685,7 @@ Algorithmus beschreiben, ergeben ihn als
 \operatorname{ggT}(a,b)\\0
 \end{pmatrix}
 =
-Q(q_n)Q(q_{n-1}) \dots Q(q_1)Q(q_0)
+Q(q_n)Q(q_{n-1}) \cdots Q(q_1)Q(q_0)
 \begin{pmatrix}a\\b\end{pmatrix}.
 \]
 Indem wir die Matrizen $Q(q_n)$ bis $Q(q_0)$ auf die linke Seite der
@@ -679,7 +695,7 @@ Gleichung schaffen, erhalten wir
 =
 Q(q_0)^{-1}
 Q(q_1)^{-1}
-\dots
+\cdots
 Q(q_{n-1})^{-1}
 Q(q_n)^{-1}
 \begin{pmatrix}\operatorname{ggT}(a,b)\\0\end{pmatrix}.
@@ -692,15 +708,14 @@ K
 =
 Q(q_0)^{-1}
 Q(q_1)^{-1}
-\dots
+\cdots
 Q(q_{n-1})^{-1}
 Q(q_n).
 \]
 Insbesondere ist die Matrix $K$ die Inverse der früher gefundenen
 Matrix $Q$.
 
-Die Berechnung der Matrix $K$ als Inverse von $Q$ ist nicht sehr
-effizient.
+Die Berechnung der Matrix $K$ als Inverse von $Q$ ist nicht schwierig.
 Genauso wie es möglich war, das Produkt $Q$ der Matrizen
 $Q(q_k)$ iterativ zu bestimmen, muss es auch eine Rekursionsformel
 für das Produkt der inversen Matrizen $Q(q_k)^{-1}$ geben.
@@ -709,7 +724,7 @@ Schreiben wir die gesuchte Matrix
 \[
 K_k
 =
-Q(q_0)^{-1}\dots Q(q_{k-1})^{-1}
+Q(q_0)^{-1}\cdots Q(q_{k-1})^{-1}
 =
 \begin{pmatrix}
 e_k & e_{k-1}\\
@@ -825,13 +840,12 @@ va
 \]
 \end{beispiel}
 
+\subsection{Kleinstes gemeinsames Vielfaches von Polynomen}
 Der erweiterte Algorithmus kann auch dazu verwendet werden,
 das kleinste gemeinsame Vielfache zweier Polynome zu berechnen.
 Dies wird zum Beispiel bei der Decodierung des Reed-Solomon-Codes in
 Kapitel~\ref{chapter:reedsolomon} verwendet.
 
-\subsubsection{Polynome
-\label{buch:endlichekoerper:eqn:polynomkgv}}
 Im Beispiel auf Seite~\pageref{buch:endlichekoerper:eqn:polynomggt}
 wird der grösste gemeinsame Teiler der Polynome
 \[
@@ -844,6 +858,8 @@ b = X^4 + X^3 -7X^2 -X + 6
 berechnet.
 Dies kann jetzt erweitert werden für die Berechnung des kleinsten
 gemeinsamen Vielfachen.
+\index{kleinstes gemeinsames Vielfaches von Polynomen}%
+\index{kgV von Polynomen}%
 
 \begin{beispiel}
 Die Berechnungstabelle nur für die Spalten $e_k$ und $f_k$ ergibt
@@ -890,8 +906,9 @@ Daraus ergibt sich das kleinste gemeinsame Vielfache auf zwei verschiedene Weise
 Die beiden Berechnungsmöglichkeiten stimmen wie erwartet überein.
 \end{beispiel}
 
-\subsubsection{Anwendung: Decodierung des Reed-Solomon-Codes}
+\subsection{Anwendung: Decodierung des Reed-Solomon-Codes}
 Der Reed-Solomon-Code verwendet Polynome zur Codierung der Daten,
+\index{Reed-Solomon-Code}%
 dies wird in Kapitel~\ref{chapter:reedsolomon} im Detail beschrieben.
 Bei der Decodierung muss der Faktor $u$ für zwei gegebene Polynome
 $n(X)$ und $r(X)$ bestimmt werden.
@@ -902,6 +919,7 @@ Algorithmus braucht.
 Daraus lässt sich genügend Information gewinnen, um die Faktoren $u$
 und $v$ zu bestimmen.
 Das Video \url{https://youtu.be/uOLW43OIZJ0} von Edmund Weitz
+\index{Weitz, Edmund}
 erklärt die Theorie hinter dieser Teilaufgabe anhand von Beispielen.
 
 \begin{beispiel}
diff --git a/buch/chapters/30-endlichekoerper/galois.tex b/buch/chapters/30-endlichekoerper/galois.tex
index c7147bf..5189dec 100644
--- a/buch/chapters/30-endlichekoerper/galois.tex
+++ b/buch/chapters/30-endlichekoerper/galois.tex
@@ -9,11 +9,11 @@
 \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$
+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.
+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
@@ -21,6 +21,8 @@ Elemente enthalten müsste.
 Wie können also endliche Körper entstehen?
 
 In diesem Abschnitt sollen die sogenannten Galois-Körper $\mathbb{F}_p$
+\index{Galois-Körper}%
+\index{Fp@$\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
@@ -51,6 +53,7 @@ Zahlen $\{0,1,2,\dots,n-1\}$ identifiziert werden kann.
 
 \begin{definition}
 Die Zahlen $a,b\in\mathbb{Z}$ heissen {\em kongruent modulo $n$},
+\index{kongruent modulo $n$}%
 geschrieben
 \[
 a\equiv b\mod n,
@@ -60,6 +63,7 @@ wenn $a-b$ durch $n$ teilbar ist, also $n|(a-b)$.
 
 Die Zahlen mit gleichem Rest sind Äquivalenzklassen der Kongruenz modulo $n$.
 Die Zahlen mit Rest $k$ modulo $n$ bilden die {\em Restklasse}
+\index{Restklasse}%
 \[
 \llbracket k\rrbracket=\{\dots,k-2n,k-n,k,k+n,k+2n,\dots\} \subset\mathbb{Z}.
 \]
@@ -90,7 +94,7 @@ 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.
+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.
 
@@ -121,8 +125,9 @@ 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}.
+Wir kommen daher zu der Forderung, dass der Ring $\mathbb{Z}/n\mathbb{Z}$ 
+nur dann ein Körper sein kann, wenn er nullteilerfrei ist.
+
 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.
@@ -130,7 +135,9 @@ Ein Körper kann also nur entstehen, wenn $n$ eine Primzahl ist.
 \begin{definition}
 \label{buch:endlichekoerper:def:galois-koerper}
 Ist $p$ eine Primzahl, dann heisst $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$
+\index{Primzahl}%
 der Galois-Körper der Ordnung $p$.
+\index{Galois-Körper}%
 \end{definition}
 
 Diese Definition ist nur gerechtfertigt, wenn $\mathbb{F}_p^*$ tatsächlich
@@ -152,6 +159,7 @@ 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.
+\index{multiplikative Inverse in $\mathbb{F}_p$}%
 
 \begin{beispiel}
 Die kleinste Primzahl grösser als $2021$ ist $p=2063$.
@@ -210,6 +218,8 @@ Inverse von $2021$ in $\mathbb{F}_{2063}$.
 \end{beispiel}
 
 \subsubsection{Der kleine Satz von Fermat}
+\index{Fermat, kleiner Satz von}%
+\index{kleiner 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.
@@ -221,6 +231,22 @@ die Potenz mit Exponent $p$ muss also mit einer früheren Potenz
 Der kleine Satz von Fermat sagt etwas genauer: die $p$-te Potenz
 von $a$ ist genau die Zahl $a$:
 
+\begin{figure}
+\centering
+\includegraphics{chapters/30-endlichekoerper/images/fermat.pdf}
+\caption{$G$ ist die Menge aller verschiedenfarbigen geschlossenen
+Perlenketten mit $p$ Perlen und $a$ Farben.
+$A$ ist die Menge aller linearen verschiedenfarbigen Ketten.
+Die Abbildung $s_i$ schneidet die Ketten an der Stelle $i$ auf,
+dadurch entstehen die Menge $A_i$, verschiedenfarbigen linearen
+Ketten der Länge $p$ mit $a$ Farben.
+Die Abbildungen $s_i$ sind injektiv, die Mengen $A_i$ haben alle
+die gleiche Anzahl Elemente.
+Genau dann ist $|A|$ durch $p$ teilbar, wenn die Mengen $A_i$
+disjunkt sind.
+\label{buch:endliche-koerper:fig:fermat}}
+\end{figure}
+
 \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^*$.
@@ -237,10 +263,10 @@ $p$ eine Primzahl ist.
 \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
+von Mathologer auf seinem Youtube-Kanal im Video
 \url{https://youtu.be/_9fbBSxhkuA} illustriert.
 
-Zum Beiweis interpretieren wir die vorkommenden Zahlen kombinatorisch.
+Zum Beweis 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.
@@ -248,26 +274,52 @@ 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 bezeichnen die Menge der nicht einfarbigen Perlenketten der
+Länge $p$ mit $a$ Farben mit $A$.
+Es ist $|A|=a^p-a$.
+
+Zu sagen, dass $a^p-a$ durch $p$ teilbar ist, ist gleichbedeutend
+damit, dass die Menge der Perlenkette in $p$
+disjunkte, gleichmächtige Mengen aufgeteilt werden kann.
+Es ist also zu zeigen, dass sich die Menge $A$ genau dann in
+disjunkte gleichmächtige Mengen zerlegen lässt, wenn $p$ eine
+Primzahl ist.
+
+Wir betrachten dazu die Menge der nicht einfarbigen, geschlossenen
+Perlenketten der Länge $p$ mit $a$ Farben.
+Einge dieser Perlenketten unterscheiden sich nur durch eine
+Drehung um einzelne Perlen.
+Sei $G$ die Menge der nicht einfarbigen, geschlossenen
+Perlenketten, die sich nicht nur um eine Drehung unterscheiden.
+
+Die Abbildung $s_i\colon G\to A$
+in Abbildung~\ref{buch:endliche-koerper:satz:fermat} 
+schneidet die Perlenkette in $G$ an der Stelle $i$ auf.
+Diese Abbildungen sond ganz offensichtlich injektiv.
+Die Bildmengen $A_i = s_i(G)$ haben daher alle gleich
+viele Elemente wie $G$: $|A_i|=|G|$.
+
+Da jede lineare Perlenkette in $A$ durch geeignetes Aufschneiden
+einer geschlossenen Perlenkette in $G$ entsteht, ist 
+\[
+A=\bigcup_{i=1}^p A_i.
+\]
 
-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$
+Wir müssen jetzt nur noch untersuchen, unter welchen Bedingungen
+die Mengen $A_i$ disjunkt sind.
+Zwei Mengen $A_i$ und $A_j$ enthalten genau dann eine
+gemeinsame Perlenkette, wenn es eine geschlossene Kette in $G$
+gibt, die beim Aufschneiden an den Stellen $i$ und $j$ die
+gleiche Kette ergeben.
+Dies bedeutet, dass sich die Farben zwischen $i$ und $j$ nach
+der Stelle $j$ wiederholen.
+Die Mengen sind also genau dann nicht disjunkt, wenn es
+peridische Ketten gibt mit einer Periode $k<p$.
+
+Da die Periode einer periodischen Kette ein Teiler von $p$
+ist, gibt es genau dann keine periodischen Ketten, wenn $p$
 eine Primzahl ist.
-
-Wir schliessen daraus, dass $a^p-a$ durch $p$ teilbar ist, genau dann,
-wenn $p$ eine Primzahl ist.
+Damit ist die Behauptung gezeigt.
 \end{proof}
 
 Der kleine Satz von Fermat kann auch dazu verwendet werden, Potenzen 
@@ -302,6 +354,8 @@ Sie ist zwar nicht unbedingt einfacher, aber manchmal nützlich für
 theoretische Überlegungen.
 
 \begin{satz}[Wilson]
+\index{Wilson, Satz von}%
+\index{Satz von Wilson}%
 Die ganze Zahl $p\ge 2$ ist genau dann eine Primzahl, wenn
 $(p-1)!\equiv -1\mod p$.
 \end{satz}
@@ -341,7 +395,7 @@ die Behauptung des Satzes.
 \end{proof}
 
 Mit dem Satz von Wilson kann man die Inverse einer beliebigen Zahl
-$a\in\mathbb{F}_p$ finden.
+$a\in\mathbb{F}_p$ wie folgt finden.
 Dazu verwendet man, dass $a$ einer der Faktoren in $(p-1)!$ ist.
 Lässt man diesen Faktor weg, erhält man eine Zahl
 \[
@@ -390,6 +444,7 @@ der Körper $\mathbb{F}_p$ in $\Bbbk$ enthalten sein muss.
 Dies ist der kleinste Teilkörper, der in $\Bbbk$ enthalten ist.
 
 \begin{definition}
+\index{Primkörper}
 Der kleinste Teilkörper eines Körpers $\Bbbk$ heisst der 
 {\em Primkörper} von $\Bbbk$.
 \end{definition}
@@ -398,7 +453,8 @@ 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
+\index{Charakteristik}%
+Die {\em 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}
@@ -411,6 +467,10 @@ Ein Körper mit Charakteristik $0$ enthält immer unendliche viele
 Elemente.
 
 \subsubsection{Teilbarkeit von Binomialkoeffizienten}
+Als Beispiel für die Auswrikung der Charakteristik auf die Arithmetik
+in einem endlichen Körper betrachten wir die Teilbarkeitseigenschaften
+der Binomialkoeffizienten.
+
 \begin{figure}
 \centering
 \includegraphics{chapters/30-endlichekoerper/images/binomial2.pdf}
@@ -437,11 +497,14 @@ sind alle Koeffizienten ausser dem ersten und letzten durch $5$ teilbar.
 \egroup
 Die Abbildung~\ref{buch:endliche-koerper:fig:binomial2} zeigt den
 Rest bei Teilung durch $2$ der Binomialkoeffizienten.
+\index{Binomialkoeffizient}%
 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.
+\index{Selbstähnlichkeit}%
+\index{Pascal-Dreieck}%
 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.
@@ -454,6 +517,10 @@ Sei $p$ eine Primzahl, dann ist
 \binom{p}{m} \equiv 0\mod p
 \]
 für $0<m<n$.
+Für $a,b\in\mathbb{Z}$ bedeutet dies
+\[
+(a+b)^p \equiv a^p + b^p\mod p.
+\]
 \end{satz}
 
 \begin{proof}[Beweis]
@@ -466,6 +533,30 @@ Für den Binomialkoeffizienten gilt
 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.
+
+In der binomischen Formel
+\[
+(a+b)^p
+=
+a^p
++
+\binom{p}{1} a^{p-1}b
++
+\binom{p}{2} a^{p-2}b^2
++
+\dots
++
+\binom{p}{p-1} ab^{p-1}
++
+b^p
+\]
+sind alle ``inneren'' Terme auf der rechten Seite durch $p$ teilbar,
+weil der Binomialkoeffizient durch $p$ teilbar ist.
+Modulo $p$ ergibt sich daher
+\[
+(a+b)^p \equiv a^p + b^p \mod p.
+\]
+Damit ist alles bewiesen.
 \end{proof}
 
 \begin{satz}
@@ -544,6 +635,7 @@ Binomialkoeffizienten der Zwischenterme der Summe
 \eqref{buch:endliche-koerper:fig:binomischeformel}
 als Elemente von $\mathbb{F}_p$.
 Daher gilt
+\index{Frobenius-Automorphismus}%
 
 \begin{satz}[Frobenius-Automorphismus]
 In einem Körper $\Bbbk$ der Charakteristik $p$ ist die Abbildung
diff --git a/buch/chapters/30-endlichekoerper/images/Makefile b/buch/chapters/30-endlichekoerper/images/Makefile
index c49fe56..bf53c29 100644
--- a/buch/chapters/30-endlichekoerper/images/Makefile
+++ b/buch/chapters/30-endlichekoerper/images/Makefile
@@ -3,10 +3,14 @@
 #
 # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
 #
-all:	binomial2.pdf binomial5.pdf
+all:	binomial2.pdf binomial5.pdf fermat.pdf
 
 binomial2.pdf:	binomial2.tex
 	pdflatex binomial2.tex
 
 binomial5.pdf:	binomial5.tex farben.tex
 	pdflatex binomial5.tex
+
+fermat.pdf:	fermat.tex
+	pdflatex fermat.tex
+
diff --git a/buch/chapters/30-endlichekoerper/images/fermat.pdf b/buch/chapters/30-endlichekoerper/images/fermat.pdf
new file mode 100644
index 0000000..4513e62
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/fermat.pdf
diff --git a/buch/chapters/30-endlichekoerper/images/fermat.tex b/buch/chapters/30-endlichekoerper/images/fermat.tex
new file mode 100644
index 0000000..6cdafaa
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/fermat.tex
@@ -0,0 +1,138 @@
+%
+% fermat.tex -- Illustration zum kleinen Satz von Fermat
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math,calc}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\s{34}
+
+\definecolor{farbe1}{rgb}{0.0,0.4,0.0}
+\definecolor{farbe2}{rgb}{0.0,1.0,1.0}
+\definecolor{farbe3}{rgb}{0.0,0.4,0.6}
+\definecolor{farbe4}{rgb}{0.0,0.0,0.8}
+\definecolor{farbe5}{rgb}{0.4,0.0,1.0}
+\definecolor{farbe6}{rgb}{0.8,0.0,0.0}
+\definecolor{farbe7}{rgb}{0.8,0.4,0.4}
+\definecolor{farbe8}{rgb}{1.0,0.8,0.0}
+
+\def\perle#1#2#3{
+	\fill[color=#3] ($#1+({#2*0.15},0)$) circle[radius=0.075];
+}
+
+\def\perlena#1#2#3#4#5#6{
+	\draw #1 -- ($#1+({0.15*9},0)$);
+	\perle{#1}{0}{#2}
+	\perle{#1}{1}{#3}
+	\perle{#1}{2}{#4}
+	\perle{#1}{3}{#5}
+	\perle{#1}{4}{#6}
+}
+\def\perlenb#1#2#3#4#5#6{
+	\perle{#1}{5}{#2}
+	\perle{#1}{6}{#3}
+	\perle{#1}{7}{#4}
+	\perle{#1}{8}{#5}
+	\perle{#1}{9}{#6}
+}
+
+\begin{scope}[xshift=3cm]
+\draw (0,0) circle[radius=4];
+\foreach \k in {-1,...,8}{
+	\draw (0,0) -- ({90+\k*\s}:4);
+}
+\foreach \k in {1,...,8}{
+	\node at ({90+\s*(\k-0.5)}:3.7) {$A_{\k\mathstrut}$};
+}
+
+\pgfmathparse{90-(360-9*\s)/2-\s}
+\xdef\b{\pgfmathresult}
+\foreach \d in {-10,-5,...,10}{
+	\fill ({\b+\d}:2.8) circle[radius=0.04];
+}
+\node at ({90-(\s/2)}:3.7) {$A_{p\mathstrut}$};
+
+\node at (-4,4) {$s_1$};
+\node at (-3.8,2.6) {$s_2$};
+\node at (-4.8,0.6) {$s_3$};
+\node at (-4.2,-2) {$s_4$};
+\node at (-4,-4) {$s_5$};
+
+\perlena{({-3*sin(-0.5*\s)-0.54},{3*cos(-0.5*\s)})}{farbe8}{farbe1}{farbe2}{farbe3}{farbe4}
+\perlenb{({-3*sin(-0.5*\s)-0.54},{3*cos(-0.5*\s)})}{farbe5}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0}
+
+\perlena{({-3*sin(0.5*\s)-0.74},{3*cos(0.5*\s)})}{farbe1}{farbe2}{farbe3}{farbe4}{farbe5}
+\perlenb{({-3*sin(0.5*\s)-0.74},{3*cos(0.5*\s)})}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8}
+
+\perlena{({-3*sin(1.5*\s)-0.74},{3*cos(1.5*\s)-0.2})}{farbe2}{farbe3}{farbe4}{farbe5}{farbe6}
+\perlenb{({-3*sin(1.5*\s)-0.74},{3*cos(1.5*\s)-0.2})}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1}
+
+\perlena{({-3*sin(2.5*\s)-0.0},{3*cos(2.5*\s)-0.0})}{farbe3}{farbe4}{farbe5}{farbe6}{farbe7}
+\perlenb{({-3*sin(2.5*\s)-0.0},{3*cos(2.5*\s)-0.0})}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1}{farbe2}
+
+\perlena{({-3*sin(3.5*\s)-0.74},{3*cos(3.5*\s)+0.2})}{farbe4}{farbe5}{farbe6}{farbe7}{black,opacity=0}
+\perlenb{({-3*sin(3.5*\s)-0.74},{3*cos(3.5*\s)+0.2})}{black,opacity=0}{farbe8}{farbe1}{farbe2}{farbe3}
+
+\perlena{({-3*sin(4.5*\s)-0.74},{3*cos(4.5*\s)})}{farbe5}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0}
+\perlenb{({-3*sin(4.5*\s)-0.74},{3*cos(4.5*\s)})}{farbe8}{farbe1}{farbe2}{farbe3}{farbe4}
+
+\perlena{({-3*sin(5.5*\s)-0.64},{3*cos(5.5*\s)})}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8}
+\perlenb{({-3*sin(5.5*\s)-0.64},{3*cos(5.5*\s)})}{farbe1}{farbe2}{farbe3}{farbe4}{farbe5}
+
+\perlena{({-3*sin(6.5*\s)-0.64},{3*cos(6.5*\s)})}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1}
+\perlenb{({-3*sin(6.5*\s)-0.64},{3*cos(6.5*\s)})}{farbe2}{farbe3}{farbe4}{farbe5}{farbe6}
+
+\perlena{({-3*sin(7.5*\s)-1.14},{3*cos(7.5*\s)+0.1})}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1}{farbe2}
+\perlenb{({-3*sin(7.5*\s)-1.14},{3*cos(7.5*\s)+0.1})}{farbe3}{farbe4}{farbe5}{farbe6}{farbe7}
+
+\node at (45:4) [above right] {$A$};
+
+\clip (-7,-4.4) rectangle (0,4.8);
+\foreach \k in {1,...,5}{
+	\pgfmathparse{20*(3-\k)}
+	\xdef\c{\pgfmathresult}
+	\pgfmathparse{90+(\k-0.5)*\s}
+	\xdef\a{\pgfmathresult}
+	\pgfmathparse{\a-180}
+	\xdef\b{\pgfmathresult}
+	\draw[->] (-7.5,0) to[out={\c},in={180+\b}] (\a:4);
+	%\node at (\a:4) [left] {$\b$};
+}
+\end{scope}
+
+\def\pearl#1#2{
+	\fill[color=#2] ($({90+(#1-0.5)*\s}:0.6)$) circle[radius=0.12];
+	\draw[line width=0.1pt] ($({90+(#1-0.5)*\s}:0.6)$) circle[radius=0.12];
+}
+
+\def\kette{
+	\draw (0,0) circle[radius=0.6];
+	\pearl{1}{farbe1}
+	\pearl{2}{farbe2}
+	\pearl{3}{farbe3}
+	\pearl{4}{farbe4}
+	\pearl{5}{farbe5}
+	\pearl{6}{farbe6}
+	\pearl{7}{farbe7}
+	\pearl{0}{farbe8}
+}
+
+\begin{scope}[xshift=-4.5cm]
+\fill[color=white] (-1.5,-2.5) rectangle (1.5,2.5);
+\draw (-1.5,-2.5) rectangle (1.5,2.5);
+\kette
+\node at (-1.5,2.5) [below right] {$G$};
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex
index 600336c..b066969 100644
--- a/buch/chapters/30-endlichekoerper/wurzeln.tex
+++ b/buch/chapters/30-endlichekoerper/wurzeln.tex
@@ -52,10 +52,10 @@ Inverse kann zum Beispiel als die inverse Matrix mit dem
 Gauss-Algorithmus berechnet werden.
 In einem zweiten Schritt zeigen wir dann, dass man die Rechnung noch
 etwas vereinfachen kann, wenn man in Polynomringen arbeitet.
-Schliesslich zeigen wir dann im
-Abschnitt~\ref{buch:subsection:zerfaellungskoerper}, wie man 
-den Prozess iterieren kann und so für beliebige Polynome immer einen
-Körper finden kann, der alle Nullstellen enthält.
+%Schliesslich zeigen wir dann im
+%Abschnitt~\ref{buch:subsection:zerfaellungskoerper}, wie man 
+%den Prozess iterieren kann und so für beliebige Polynome immer einen
+%Körper finden kann, der alle Nullstellen enthält.
 Wir beginnen in Abschnitt~\ref{buch:subsection:irreduziblepolynome}
 damit, die Polynome, die für die Konstruktion in Frage kommen, etwas
 genauer zu charakterisieren.
@@ -608,7 +608,17 @@ $J$ mit $I\subset J\subset R$ entweder $I=J$ oder $J=R$ gilt.
 Die Ideale $p\mathbb{Z}\subset \mathbb{Z}$ sind maximal genau dann, wenn
 $p$ eine Primzahl ist.
 
-TODO: XXX Begründung
+Ist nämlich $p=n_1n_2$ eine Faktorisierung, dann ist
+$\mathbb{Z}\supset n_1\mathbb{Z} \supset p\mathbb{Z}$ 
+und $n_1\mathbb{Z}$ ist ein grössers Ideal als $p\mathbb{Z}$,
+d.~h.~$p\mathbb{Z}$ ist nicht maximal.
+
+In $\mathbb{Z}$ sind alle Ideale von der Form $n\mathbb{Z}$.
+Wenn es also ein Ideal $I\supset p\mathbb{Z}$ gibt, welches
+$p\mathbb{Z}$ echt enthält, dann gibt es $n\in\mathbb{Z}$ derart,
+dass $n\mathbb{Z} \subset p\mathbb{Z}$.
+Dies ist gleichbedeutend damit, dass $n$ ein echter Teiler von $p$
+ist, also ist $p$ keine Primzahl.
 \end{beispiel}
 
 \begin{satz}
@@ -616,6 +626,23 @@ Der Ring $R/I$ ist genau dann ein Körper, wenn $I$ ein maximales Ideal ist.
 \end{satz}
 
 \begin{proof}[Beweis]
+Nehmen wir zunächst an, dass $I$ ein maximales Ideal ist.
+Damit $R/I$ ein Körper ist, muss jedes von $0$ verschiedene Element 
+eine multiplikatives Inverses haben.
+Sei als $a\in R\setminus I$, dann ist $a+I$ ein von $0$ verschiedenes
+Körperelement.
+Die Menge $Ra+I$ ist dann ein Ideal von $R$, welches $I$ echt enthält.
+Weil $I$ maximal ist, ist $Ra+I=R$, also gibt es ein Element $b\in I$
+derart, dass $ab+I=1+I$, d.~h.~$b+I$ ist das gesuchte multiplikative 
+Inverse.
+
+Sei nun umgekehrt $R/I$ ein Körper und $J\supset I$ sei ein Ideal,
+welches $I$ echt enhält.
+Sei $a\in J\setminus I$.
+Da $R/I$ ein Körper ist, ist $a+I$ invertierbar, es gibt also ein
+$b\in R$ mit $ab+I=1+I$.
+Da $a\in J$ folgt $Ra\subset J$.
+Andererseits ist $1\in Ra$, also ist $J=R$ und das Ideal $J$ ist maximal.
 \end{proof}
 
 Ein irreduzibles Polynom $m\in\Bbbk[X]$ erzeugt ein maximales Ideal,
@@ -894,10 +921,3 @@ Dieser Spezialfall ist für die praktische Anwendung in der Kryptographie
 von besonderer Bedeutung, daher wird er im 
 In Kapitel~\ref{buch:chapter:kryptographie} genauer untersucht.
 
-\subsection{Zerfällungskörper
-\label{buch:subsection:zerfaellungskoerper}}
-XXX TODO
-
-
-
-