aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/30-endlichekoerper
diff options
context:
space:
mode:
authorLordMcFungus <mceagle117@gmail.com>2021-03-22 18:05:11 +0100
committerGitHub <noreply@github.com>2021-03-22 18:05:11 +0100
commit76d2d77ddb2bed6b7c6b8ec56648d85da4103ab7 (patch)
tree11b2d41955ee4bfa0ae5873307c143f6b4d55d26 /buch/chapters/30-endlichekoerper
parentmore chapter structure (diff)
parentadd title image (diff)
downloadSeminarMatrizen-76d2d77ddb2bed6b7c6b8ec56648d85da4103ab7.tar.gz
SeminarMatrizen-76d2d77ddb2bed6b7c6b8ec56648d85da4103ab7.zip
Merge pull request #1 from AndreasFMueller/master
update
Diffstat (limited to '')
-rw-r--r--buch/chapters/30-endlichekoerper/Makefile.inc6
-rw-r--r--buch/chapters/30-endlichekoerper/beispiele/inverse.m15
-rw-r--r--buch/chapters/30-endlichekoerper/chapter.tex17
-rw-r--r--buch/chapters/30-endlichekoerper/euklid.tex617
-rw-r--r--buch/chapters/30-endlichekoerper/galois.tex553
-rw-r--r--buch/chapters/30-endlichekoerper/images/Makefile12
-rw-r--r--buch/chapters/30-endlichekoerper/images/binomial2.pdfbin0 -> 19246 bytes
-rw-r--r--buch/chapters/30-endlichekoerper/images/binomial2.tex306
-rw-r--r--buch/chapters/30-endlichekoerper/images/binomial5.pdfbin0 -> 26050 bytes
-rw-r--r--buch/chapters/30-endlichekoerper/images/binomial5.tex379
-rw-r--r--buch/chapters/30-endlichekoerper/images/farben.tex4
-rw-r--r--buch/chapters/30-endlichekoerper/rechnungen/euinv.maxima31
-rw-r--r--buch/chapters/30-endlichekoerper/rechnungen/invbeispiel.maxima81
-rw-r--r--buch/chapters/30-endlichekoerper/rechnungen/inverse.maxima35
-rw-r--r--buch/chapters/30-endlichekoerper/rechnungen/multiplikation.maxima38
-rw-r--r--buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex102
-rw-r--r--buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex9
-rw-r--r--buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex72
-rw-r--r--buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex234
-rw-r--r--buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m22
-rw-r--r--buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex205
-rw-r--r--buch/chapters/30-endlichekoerper/wurzeln.tex894
22 files changed, 3631 insertions, 1 deletions
diff --git a/buch/chapters/30-endlichekoerper/Makefile.inc b/buch/chapters/30-endlichekoerper/Makefile.inc
index 1118fb0..4cd75b2 100644
--- a/buch/chapters/30-endlichekoerper/Makefile.inc
+++ b/buch/chapters/30-endlichekoerper/Makefile.inc
@@ -5,6 +5,12 @@
#
CHAPTERFILES = $(CHAPTERFILES) \
+ chapters/30-endlichekoerper/uebungsaufgaben/3001.tex \
+ chapters/30-endlichekoerper/uebungsaufgaben/3002.tex \
+ chapters/30-endlichekoerper/uebungsaufgaben/3003.tex \
+ chapters/30-endlichekoerper/uebungsaufgaben/3004.tex \
+ chapters/30-endlichekoerper/uebungsaufgaben/3005.tex \
+ chapters/30-endlichekoerper/euklid.tex \
chapters/30-endlichekoerper/galois.tex \
chapters/30-endlichekoerper/wurzeln.tex \
chapters/30-endlichekoerper/chapter.tex
diff --git a/buch/chapters/30-endlichekoerper/beispiele/inverse.m b/buch/chapters/30-endlichekoerper/beispiele/inverse.m
new file mode 100644
index 0000000..69c6429
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/beispiele/inverse.m
@@ -0,0 +1,15 @@
+#
+# inverse.m -- Inverse mod 2063 berechnen
+#
+# (c) Prof Dr Andreas Müller, Hochschule Rapperswil
+#
+function retval = Q(q)
+ retval = [ 0, 1; 1, -q ];
+end
+
+P = eye(2)
+P = Q(1) * P
+P = Q(48) * P
+P = Q(8) * P
+P = Q(2) * P
+P = Q(2) * P
diff --git a/buch/chapters/30-endlichekoerper/chapter.tex b/buch/chapters/30-endlichekoerper/chapter.tex
index 6dfbaef..1a0a323 100644
--- a/buch/chapters/30-endlichekoerper/chapter.tex
+++ b/buch/chapters/30-endlichekoerper/chapter.tex
@@ -20,6 +20,10 @@ die diese Eigenschaft nicht haben.
Nicht überraschend werden die ersten derartigen Körper, die wir
in Abschnitt~\ref{buch:section:galoiskoerper} konstruieren werden,
endlich viele Elemente haben.
+Als Hilfsmittel für die Definition der Division in diesem Körper wird
+als Vorbereitung in Abschnitt~\ref{buch:section:euklid} der
+euklidische Algorithmus vorgestellt, wobei auch eine besonders zum
+Thema dieses Buches passende Beschreibung in Matrixform angegeben wird.
Zu diesen sogenannten Galois-Körpern können wir dann weitere Elemente
hinzufügen, wie das in Abschnitt ~\ref{buch:section:wurzeln}
gezeigt wird.
@@ -27,8 +31,19 @@ Diese Technik, die auch für den Körper $\mathbb{Q}$ funktioniert, erlaubt
dafür zu sorgen, dass in einem Körper gewisse algebraische Gleichungen
lösbar werden.
-
+\input{chapters/30-endlichekoerper/euklid.tex}
\input{chapters/30-endlichekoerper/galois.tex}
\input{chapters/30-endlichekoerper/wurzeln.tex}
+\section*{Übungsaufgaben}
+\rhead{Übungsaufgaben}
+\aufgabetoplevel{chapters/30-endlichekoerper/uebungsaufgaben}
+\begin{uebungsaufgaben}
+\uebungsaufgabe{3004}
+\uebungsaufgabe{3003}
+\uebungsaufgabe{3002}
+\uebungsaufgabe{3001}
+\uebungsaufgabe{3005}
+\end{uebungsaufgaben}
+
diff --git a/buch/chapters/30-endlichekoerper/euklid.tex b/buch/chapters/30-endlichekoerper/euklid.tex
new file mode 100644
index 0000000..db326f8
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/euklid.tex
@@ -0,0 +1,617 @@
+%
+% euklid.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Der euklidische Algorithmus
+\label{buch:section:euklid}}
+\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
+\[
+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.
+
+%
+% Der euklidische Algorithmus für ganze Zahlen
+%
+\subsection{Ganze 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$.
+Wir schreiben $g|a$ für ``$g$ ist Teiler von $a$'' oder ``$g$ teilt $a$'',
+gesucht ist also die grösste ganze Zahl $g$ derart, dass $g|a$ und $g|b$.
+
+Ist $b|a$, dann ist offenbar $b$ der grösste gemeinsame Teiler von $a$
+und $b$.
+Im Allgemeinen wird der grösste gemeinsame Teiler aber kleiner sein.
+Wir teilen daher $a$ durch $b$, was nur mit Rest möglich ist.
+Es gibt ganze Zahlen $q$, der Quotient, und $r$, der Rest, derart, dass
+\begin{equation}
+a = qb+ r
+\qquad \Rightarrow \qquad
+r = a - qb.
+\label{lifting:euklid:raqb}
+\end{equation}
+Nach Definition des Restes ist $r < b$.
+Da der grösste gemeinsame Teiler sowohl $a$ als auch $b$ teilt, muss er
+wegen~\eqref{lifting:euklid:raqb} auch $r$ teilen.
+Somit haben wir das Problem, den grössten gemeinsamen Teiler von $a$ und
+$b$ zu finden, auf das ``kleinere'' Problem zurückgeführt, den grössten
+gemeinsamen Teiler von $b$ und $r$ zu finden.
+
+Um den eben beschriebenen Schritt zu wiederholen, wählen wir die folgende
+Notation.
+Wir schreiben $a_0=a$ und $b_0=b$.
+Im ersten Schritt finden wird $q_0$ und $r_0$ derart,
+dass $a_0-q_0b_0 = r_0$.
+Dann setzen wir $a_1=b_0$ und $b_1=r_0$.
+Mit $a_1$ und $b_1$ wiederholen wir den Divisionsschritt, der einen
+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}
+\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$.
+
+\begin{beispiel}
+\label{buch:endlichekoerper:beispiel1}
+Wir bestimmen den grössten gemeinsamen Teiler von $76415$ und $23205$
+mit Hilfe des eben beschriebenen Algorithmus.
+Wir schreiben die gefundenen Zahlen in eine Tabelle:
+\begin{center}
+\renewcommand{\arraystretch}{1.1}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
+\hline
+k& a_k& b_k& q_k& r_k\\
+\hline
+0&76415&23205& 3&6800\\
+1&23205& 6800& 3&2805\\
+2& 6800& 2805& 2&1190\\
+3& 2805& 1190& 2& 425\\
+4& 1190& 425& 2& 340\\
+5& 425& 340& 1& 85\\
+6& 340& 85& 4& 0\\
+\hline
+\end{tabular}
+\end{center}
+Der Algorithmus bricht also mit dem letzten Rest $r_n=85$ ab, dies
+ist der grösste gemeinsame Teiler.
+\end{beispiel}
+
+Die oben protokollierten Werte von $q_k$ werden für die Bestimmung
+des grössten gemeinsamen Teilers nicht benötigt.
+Wir können sie aber verwenden, um die Zahlen $s$ und $t$ zu bestimmen.
+
+\begin{beispiel}
+Wir drücken die Reste im obigen Beispiel durch die Zahlen $a_k$, $b_k$ und
+$q_k$ aus und setzen sie in den Ausdruck $g=a_5-q_5b_5$ ein, bis wir
+einen Ausdruck in $a_0$ und $b_0$ für $g$ finden:
+\begin{align*}
+r_5&=a_5-q_5 b_5=a_5-1\cdot b_5& g &= a_5 - 1 \cdot b_5 = b_4 - 1 \cdot r_4
+\\
+r_4&=a_4-q_4 b_4=a_4-2\cdot b_4& &= b_4 - (a_4 -2b_4)
+ = -a_4 +3b_4 = -b_3 + 3r_3
+\\
+r_3&=a_3-q_3 b_3=a_3-2\cdot b_3& &= -b_3 + 3(a_3-2b_3)
+ = 3a_3 - 7b_3 = 3b_2 -7r_2
+\\
+r_2&=a_2-q_2 b_2=a_2-2\cdot b_2& &= 3b_2 -7(a_2-2b_2)
+ = -7a_2 + 17b_2 = -7b_1 + 17r_1
+\\
+r_1&=a_1-q_1 b_1=a_1-3\cdot b_1& &= -7b_1 + 17(a_1-3b_1)
+ = 17a_1 - 58b_1 = 17 b_0 - 58 r_0
+\\
+r_0&=a_0-q_0 b_0=a_0-3\cdot b_0& &= 17b_0 - 58(a_0t-3b_0)
+ = -58a_0+191b_0
+\end{align*}
+Tatsächlich gilt
+\[
+-58\cdot 76415 + 191 \cdot 23205 = 85,
+\]
+die Zahlen $t=-58$ und $s=191$ sind also genau die eingangs versprochenen
+Faktoren.
+\end{beispiel}
+
+%
+% Matrixschreibeweise für den euklidischen Algorithmus
+%
+\subsection{Matrixschreibweise
+\label{buch:endlichekoerper:subsection:matrixschreibweise}}
+Die Durchführung des euklidischen Algorithmus lässt sich besonders elegant
+in Matrixschreibweise dokumentieren.
+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
+\[
+\begin{pmatrix} a_{k+1} \\ b_{k+1} \end{pmatrix}
+=
+\begin{pmatrix} b_k \\ r_k \end{pmatrix}
+=
+\begin{pmatrix} 0 & 1 \\ 1 & -q_k \end{pmatrix}
+\begin{pmatrix} a_{k} \\ b_{k} \end{pmatrix}
+\]
+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:
+\begin{align*}
+\begin{pmatrix} 23205 \\ 6800 \end{pmatrix}
+&=
+\begin{pmatrix} 0&1\\1&-3 \end{pmatrix}
+\begin{pmatrix} 76415 \\ 23205 \end{pmatrix}
+\\
+\begin{pmatrix} 6800 \\ 2805 \end{pmatrix}
+&=
+\begin{pmatrix} 0&1\\1&-3 \end{pmatrix}
+\begin{pmatrix} 23205 \\ 6800 \end{pmatrix}
+\\
+\begin{pmatrix} 2805 \\ 1190 \end{pmatrix}
+&=
+\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
+\begin{pmatrix} 6800 \\ 2805 \end{pmatrix}
+\\
+\begin{pmatrix} 1190 \\ 425 \end{pmatrix}
+&=
+\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
+\begin{pmatrix} 2805 \\ 1190 \end{pmatrix}
+\\
+\begin{pmatrix} 425 \\ 340 \end{pmatrix}
+&=
+\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
+\begin{pmatrix} 1190 \\ 425 \end{pmatrix}
+\\
+\begin{pmatrix} 340 \\ 85 \end{pmatrix}
+&=
+\begin{pmatrix} 0&1\\1&-1 \end{pmatrix}
+\begin{pmatrix} 425 \\ 340 \end{pmatrix}
+\\
+\begin{pmatrix} 85 \\ 0 \end{pmatrix}
+&=
+\begin{pmatrix} 0&1\\1&-4 \end{pmatrix}
+\begin{pmatrix} 340 \\ 85 \end{pmatrix}
+=
+\begin{pmatrix}g\\0\end{pmatrix}.
+\end{align*}
+
+\begin{definition}
+Wir kürzen
+\[
+Q(q_k) = \begin{pmatrix} 0 & 1 \\ 1 & -q_k \end{pmatrix}
+\]
+ab.
+\end{definition}
+
+Mit dieser Definition lässt sich der euklidische Algorithmus wie folgt
+beschreiben.
+
+\begin{algorithmus}[Euklid]
+\label{lifting:euklid}
+Der Algorithmus operiert auf zweidimensionalen Zustandsvektoren
+$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 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
+verschwindet.
+Die erste Komponente ist dann der gesuchte grösste gemeinsame Teiler.
+\end{enumerate}
+\end{algorithmus}
+
+Auch die Berechnung der Zahlen $s$ und $t$ lässt sich jetzt leichter verstehen.
+Nach Algorithmus~\ref{lifting:euklid} ist
+\[
+\begin{pmatrix} g \\ 0 \end{pmatrix}
+=
+Q(q_n)Q(q_{n-1})\cdots Q(q_0)
+\begin{pmatrix} a \\ b \end{pmatrix}.
+\]
+Schreiben wir $Q=Q(q_n)Q(q_{n-1})\cdots Q(q_0)$, dann enthält die Matrix
+$Q$ in der erste Zeile die ganzen Zahlen $s$ und $t$, mit denen sich der
+grösste gemeinsame Teiler aus $a$ und $b$ darstellen lässt:
+\[
+Q =
+\begin{pmatrix}
+s&t\\
+q_{21}&q_{22}
+\end{pmatrix}
+\qquad\Rightarrow\qquad
+\bigg\{
+\quad
+\begin{aligned}
+g&=sa+tb\\
+0&=q_{21}a+q_{22}b.
+\end{aligned}
+\]
+
+\begin{beispiel}
+Wir verifizieren die Behauptung durch Nachrechnen:
+\begin{align*}
+Q
+&=
+\begin{pmatrix} 0&1 \\ 1&-q_n\end{pmatrix}
+\begin{pmatrix} 0&1 \\ 1&-q_{n-1}\end{pmatrix}
+\cdots
+\begin{pmatrix} 0&1 \\ 1&-q_{0}\end{pmatrix}
+\\
+&=
+\underbrace{
+\begin{pmatrix} 0&1 \\ 1& -4 \end{pmatrix}
+\begin{pmatrix} 0&1 \\ 1& -1 \end{pmatrix}
+}_{}
+\underbrace{
+\begin{pmatrix} 0&1 \\ 1& -2 \end{pmatrix}
+\begin{pmatrix} 0&1 \\ 1& -2 \end{pmatrix}
+}_{}
+\underbrace{
+\begin{pmatrix} 0&1 \\ 1& -2 \end{pmatrix}
+\begin{pmatrix} 0&1 \\ 1& -3 \end{pmatrix}
+}_{}
+\begin{pmatrix} 0&1 \\ 1& -3 \end{pmatrix}
+\\
+&=
+\underbrace{
+\begin{pmatrix} 1 & -1 \\ -4 & 5 \end{pmatrix}
+\begin{pmatrix} 1 & -2 \\ -2 & 5 \end{pmatrix}
+}_{}
+\underbrace{
+\begin{pmatrix} 1 & -2 \\ -3 & 7 \end{pmatrix}
+\begin{pmatrix} 0 & 1 \\ 1 & -3 \end{pmatrix}
+}_{}
+\\ &=
+\begin{pmatrix} 3 & -7 \\ -14 & 33 \end{pmatrix}
+\begin{pmatrix} -3 & 10 \\ 7 & -23 \end{pmatrix}
+=
+\begin{pmatrix} -58 & 191 \\ 273 & -899 \end{pmatrix}.
+%(%i9) Q6 . Q5
+% [ 1 - 1 ]
+%(%o9) [ ]
+% [ - 4 5 ]
+%(%i10) Q4 . Q3
+% [ 1 - 2 ]
+%(%o10) [ ]
+% [ - 2 5 ]
+%(%i11) Q2 . Q1
+% [ 1 - 3 ]
+%(%o11) [ ]
+% [ - 2 7 ]
+%(%i12) Q6 . Q5 . Q4 . Q3
+% [ 3 - 7 ]
+%(%o12) [ ]
+% [ - 14 33 ]
+%(%i13) Q2 . Q1 . Q0
+% [ - 3 10 ]
+%(%o13) [ ]
+% [ 7 - 23 ]
+%(%i14) Q6 . Q5 . Q4 . Q3 . Q2 . Q1 . Q0
+% [ - 58 191 ]
+%(%o14) [ ]
+% [ 273 - 899 ]
+\end{align*}
+In der zweiten Zeile findet man Zahlen, die $a$ und $b$ zu 0 kombinieren:
+\[
+273 \cdot 76415 - 899 \cdot 23205 = 0,
+\]
+in der ersten stehen die Zahlen $s=-58$ und $t=191$ und tatsächlich
+ergibt
+\[
+ta+sb = -58\cdot 76415 + 191\cdot 23205 = 85 = g
+\]
+den grössten gemeinsamen Teiler von 76415 und 23205.
+\end{beispiel}
+
+Die Wirkung der Matrix
+\[
+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
+\label{buch:endlichekoerper:subsection:matrixschreibweise}}
+Die Durchführung des euklidischen Algorithmus mit Hilfe der Matrizen
+$Q(q_k)$ ist etwas unhandlich.
+In diesem Abschnitt sollen die Matrizenprodukte daher in einer Form
+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.
+Dazu beachten wir zunächst, dass die Multiplikation mit der Matrix
+$Q(q_k)$ die zweite Zeile in die erste Zeile verschiebt:
+\[
+Q(q_k)
+\begin{pmatrix}
+u&v\\
+c&d\\
+\end{pmatrix}
+=
+\begin{pmatrix}0&1\\1&-q_k\end{pmatrix}
+\begin{pmatrix}
+u&v\\
+c&d
+\end{pmatrix}
+=
+\begin{pmatrix}
+c&d\\
+u-q_kc&v-q_kd
+\end{pmatrix}.
+\]
+Die Matrizen
+\[
+Q_k = Q(q_k)Q(q_{k-1})\dots Q(q_0)
+\]
+haben daher jeweils für aufeinanderfolgende Werte vo $k$ eine Zeile
+gemeinsam.
+Wir bezeichnen die Einträge der ersten Zeile der Matrix $Q_k$ mit
+$c_k$ und $d_k$.
+Es gilt dann
+\[
+Q_k
+=
+\begin{pmatrix}
+c_{k} &d_{k} \\
+c_{k+1}&d_{k+1}
+\end{pmatrix}
+=
+Q(q_k)
+\begin{pmatrix}
+c_{k-1}&d_{k-1}\\
+c_{k} &d_{k}
+\end{pmatrix}
+\]
+Daraus ergeben sich die Rekursionsformeln
+\begin{equation}
+\begin{aligned}
+c_{k+1}&=c_{k-1}-q_kc_k\\
+d_{k+1}&=d_{k-1}-q_kd_k.
+\end{aligned}
+\label{buch:endlichekoerper:eqn:cdrekursion}
+\end{equation}
+Die Auswertung des Matrizenproduktes von links nach rechts beginnt mit
+der Einheitsmatrix, es ist
+\[
+Q_0
+=
+Q(q_0) I
+=
+\begin{pmatrix}
+0&1\\
+1&-q_0
+\end{pmatrix}
+\begin{pmatrix}
+1&0\\0&1\end{pmatrix},
+\]
+woraus man ablesen kann, dass
+\begin{equation}
+Q_{-1}
+=
+\begin{pmatrix}
+c_{-1}&d_{-1}\\
+c_0&d_0
+\end{pmatrix}
+=
+\begin{pmatrix}
+1&0\\
+0&1
+\end{pmatrix}
+\label{buch:endlichekoerper:eqn:cdinitial}
+\end{equation}
+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
+Spalte mit Hilfe der
+Rekursionsformeln~\eqref{buch:endlichekoerper:eqn:cdrekursion}
+aus den initialen Werten~\eqref{buch:endlichekoerper:eqn:cdinitial}
+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$
+Wir schreiben die gefundenen Zahlen in eine Tabelle:
+\begin{center}
+\renewcommand{\arraystretch}{1.1}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
+\hline
+k& a_k& b_k& q_k& r_k& c_k& d_k\\
+\hline
+ & & & & & 1& 0\\
+0& 76415& 23205& 3& 6800& 0& 1\\
+1& 23205& 6800& 3& 2805& 1& -3\\
+2& 6800& 2805& 2& 1190& -3& 10\\
+3& 2805& 1190& 2& 425& 7& -23\\
+4& 1190& 425& 2& 340& -17& 56\\
+5& 425& 340& 1& 85& 41& -135\\
+6& 340& 85& 4& 0& -58& 191\\
+7& 85& 0& & & 273& -899\\
+\hline
+\end{tabular}
+\end{center}
+Aus den letzten zwei Spalten der Tabelle kann man ablesen, dass
+\begin{align*}
+-58\cdot 76415 + 191\cdot 23205 &= 85\\
+273\cdot 76415 - 899\cdot 23205 &= 0,
+\end{align*}
+wie erwartet.
+Die gesuchten Zahlen $s$ und $t$ sind also $s=-58$ und $t=191$.
+\end{beispiel}
+
+Die Matrizen $Q_k$ kann man auch as der Tabelle ablesen, sie bestehen
+aus den vier Elementen in den Zeilen $k$ und $k+1$ in den
+Spalten $c_k$ und $d_k$.
+Auf jeder Zeile gilt $b_k = c_ka_0 + d_kb_0$, für $k>0$ ist dies
+$c_ka_0+d_kb_0=r_{k-1}$.
+
+Bis jetzt gingen wir immer davon aus, dass $a>b$ ist.
+Dies ist jedoch nicht nötig, wie die Durchführung des Algorithmus
+für das obige Beispiel mit vertauschten Werten von $a$ und $b$ zeigt.
+Wir bezeichnen die Elemente zur Unterscheidung von der ursprünglichen
+Durchführung mit einem Strich:
+\begin{center}
+\renewcommand{\arraystretch}{1.1}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
+\hline
+k& a_k'& b_k'& q_k'& r_k'& c_k'& d_k'\\
+\hline
+ & & & & & 1& 0\\
+0& 23205& 76415& 0& 23205& 0& 1\\
+1& 76415& 23205& 3& 6800& 1& 0\\
+2& 23205& 6800& 3& 2805& -3& 1\\
+3& 6800& 2805& 2& 1190& 10& -3\\
+4& 2805& 1190& 2& 425& -23& 7\\
+5& 1190& 425& 2& 340& 56& -17\\
+6& 425& 340& 1& 85& -135& 41\\
+7& 340& 85& 4& 0& 191& -58\\
+8& 85& 0& & & -899& 273\\
+\hline
+\end{tabular}
+\end{center}
+Da für $a<b$ der erste Quotient $q_0'=0$ ist, werden die ersten neuen
+Elemente $c_1'=1=d_0$ und $d_1'=0=c_0$ sein.
+Die nachfolgenden Quotienten sind genau die gleichen, also $q_k = q_{k+1}'$
+und damit werden auch
+\[
+c_{k}=d_{k+1}' \qquad\text{und}\qquad d_{k} = c_{k+1}'
+\]
+sein.
+Man findet also die gleichen Einträge in einer Tabelle, die eine Zeile
+mehr hat und in der die letzten zwei Spalten gegenüber der ursprünglichen
+Tabelle vertauscht wurden.
+
+%
+% Der euklidische Algorithmus für Polynome
+%
+\subsection{Polynome}
+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.
+Es gelten sogar ähnlich interessante Gesetzmässigkeiten, wenn man für
+die Koeffizienten ganze Zahlen zulässt.
+Dann wird das Problem der Faktorisierung allerdings verkompliziert
+durch das Problem der Teilbarkeit der Koeffizienten.
+Dieses Problem entfällt, wenn man die Koeffizienten aus einem
+Bereich wählt, in dem Teilbarkeit kein Problem ist, also in einem Körper.}
+verhält
+sich bezüglich Teilbarkeit ganz genau gleich wie die ganzen Zahlen.
+Insbesondere ist der euklidische Algorithmus genauso wie die
+Matrixschreibweise auch für Polynome durchführbar.
+
+\begin{beispiel}
+Wir berechnen als Beispiel den grössten gemeinsamen Teiler
+der Polynome
+\[
+a = X^4 - 2X^3 -7 X^2 + 8X + 12,
+\qquad
+b = X^4 + X^3 -7X^2 -X + 6.
+\]
+Wir erstellen wieder die Tabelle der Reste
+\begin{center}
+\renewcommand{\arraystretch}{1.4}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
+\hline
+k& a_k& b_k& q_k& r_k\\
+\hline
+0& X^4 - 2X^3 -7 X^2 + 8X + 12& X^4 + X^3 -7X^2 -X + 6& 1&-3X^3+9X+6\\
+1&X^4+X^3-7X^2-X+6 &-3X^3+9X+6 &-\frac13X-\frac13&-4X^2+4X+8\\
+2&-3X^3+9X+6 &-4X^2+4X+8& \frac34 X + \frac34& 0\\
+\hline
+\end{tabular}
+\end{center}
+Daraus kann man ablesen, dass $-4x^2+4x+8$ grösster gemeinsamer Teiler ist.
+Normiert auf einen führenden Koeffizienten $1$ ist dies das Polynom
+$x^2-x+2=(x+2)(x-1)$.
+
+Wir berechnen auch noch die Polynome $s$ und $t$.
+Dazu müssen wir die Matrizen $Q(q_k)$ miteinander multiplizieren:
+\begin{align*}
+Q
+&=Q(q_2) Q(q_1) Q(q_0)
+\\
+&=
+\begin{pmatrix} 0 & 1 \\ 1 & -\frac34(X+1) \end{pmatrix}
+\begin{pmatrix} 0 & 1 \\ 1 & \frac13(X+1) \end{pmatrix}
+\begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix}
+\\
+&=
+% [ x 1 2 x ]
+% [ - + - - - - ]
+% [ 3 3 3 3 ]
+%(%o22) [ ]
+% [ 2 2 ]
+% [ x x 3 x x 3 ]
+% [ (- --) - - + - -- - - - - ]
+% [ 4 2 4 4 4 2 ]
+\begin{pmatrix}
+\frac13(X+1)&-\frac13(X-2)\\
+-\frac14(X^2+2X-3)&\frac14(X^2-X-6)
+\end{pmatrix}.
+\end{align*}
+In der ersten Zeile finden wir die Polynome $t(X)$ und $s(X)$, mit denen
+\begin{align*}
+ta+sb
+&=
+\frac13(X+1)
+(X^4-2X^3-7X^2+8X+12)
+-\frac13(X-2)
+(X^4+X^3-7X^2-X+6)
+\\
+&=
+-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
+$a$ und $b$ gleich werden:
+\begin{align*}
+q_{21}a+q_{22}b
+&=
+-\frac14(X^2+2X-3)
+(X^4-2X^3-7X^2+8X+12)
++\frac14(X^2-X-6)
+(X^4+X^3-7X^2-X+6)
+\\
+&=0.
+\qedhere
+\end{align*}
+Man kann natürlich den grössten gemeinsamen Teiler auch mit Hilfe einer
+Faktorisierung der Polynome $a$ und $b$ finden:
+\begin{align*}
+&\text{Faktorisierung von $a$:}&
+a &= (X-3) (X-2)\phantom{(X-1)}(X+1) (X+2) \phantom{(X+3)}\\
+&\text{Faktorisierung von $b$:}&
+b &=\phantom{(X-3)}(X-2) (X-1) (X+1)\phantom{(X+2)} (X+3) \\
+&\text{gemeinsame Faktoren:}&
+g &=\phantom{(X-3)}(X-2)\phantom{(X-1)}(X+1)\phantom{(X+2)}\phantom{(X+3)}
+ = X^2 -X + 2\\
+&&
+v=a/g&= (X-3)\phantom{(X-2)(X-1)(X+1)} (X+2) \phantom{(X+3)}
+ = X^2-X-6 \\
+&&
+u=b/g&=\phantom{(X-3)(X-2)} (X-1)\phantom{(X+1)(X+2)}(X+3)
+ = X^2+2X-3
+\end{align*}
+Aus den letzten zwei Zeilen folgt
+$ua-vb = ab/g - ab/g = 0$, wie erwartet.
+\end{beispiel}
+
+
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}
diff --git a/buch/chapters/30-endlichekoerper/images/Makefile b/buch/chapters/30-endlichekoerper/images/Makefile
new file mode 100644
index 0000000..c49fe56
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/Makefile
@@ -0,0 +1,12 @@
+#
+# Makefile
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+all: binomial2.pdf binomial5.pdf
+
+binomial2.pdf: binomial2.tex
+ pdflatex binomial2.tex
+
+binomial5.pdf: binomial5.tex farben.tex
+ pdflatex binomial5.tex
diff --git a/buch/chapters/30-endlichekoerper/images/binomial2.pdf b/buch/chapters/30-endlichekoerper/images/binomial2.pdf
new file mode 100644
index 0000000..92be742
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/binomial2.pdf
Binary files differ
diff --git a/buch/chapters/30-endlichekoerper/images/binomial2.tex b/buch/chapters/30-endlichekoerper/images/binomial2.tex
new file mode 100644
index 0000000..77ccb57
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/binomial2.tex
@@ -0,0 +1,306 @@
+%
+% binomial2.tex -- Parität der Binomialkoeffizienten
+%
+% (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}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\s{0.37}
+\pgfmathparse{\s*sqrt(3)/2}
+\xdef\ys{\pgfmathresult}
+\pgfmathparse{\s/2}
+\xdef\xs{\pgfmathresult}
+
+%
+% #1 = n
+% #2 = k
+%
+\def\dreieck#1#2{
+ \fill[color=black] ({\xs*(-#1+2*#2)},{-\ys*#1})
+ -- ({\xs*(-#1+2*#2-1)},{-\ys*(#1+1)})
+ -- ({\xs*(-#1+2*#2+1)},{-\ys*(#1+1)}) -- cycle;
+}
+\def\zeile#1{
+ \fill[color=red!40]
+ ({\xs*(-#1)},{-\ys*#1})
+ -- ({\xs*(-#1-1)},{-\ys*(#1+1)})
+ -- ({\xs*(#1+1)},{-\ys*(#1+1)})
+ -- ({\xs*(#1)},{-\ys*#1}) -- cycle;
+}
+
+\zeile{2}
+\zeile{4}
+\zeile{8}
+\zeile{16}
+\zeile{32}
+
+\dreieck{0}{0}
+
+\dreieck{1}{0}
+\dreieck{1}{1}
+
+\dreieck{2}{0}
+\dreieck{2}{2}
+
+\dreieck{3}{0}
+\dreieck{3}{1}
+\dreieck{3}{2}
+\dreieck{3}{3}
+
+\dreieck{4}{0}
+\dreieck{4}{4}
+
+\dreieck{5}{0}
+\dreieck{5}{1}
+\dreieck{5}{4}
+\dreieck{5}{5}
+
+\dreieck{6}{0}
+\dreieck{6}{2}
+\dreieck{6}{4}
+\dreieck{6}{6}
+
+\dreieck{7}{0}
+\dreieck{7}{1}
+\dreieck{7}{2}
+\dreieck{7}{3}
+\dreieck{7}{4}
+\dreieck{7}{5}
+\dreieck{7}{6}
+\dreieck{7}{7}
+
+\dreieck{8}{0}
+\dreieck{8}{8}
+
+\dreieck{9}{0}
+\dreieck{9}{1}
+\dreieck{9}{8}
+\dreieck{9}{9}
+
+\dreieck{10}{0}
+\dreieck{10}{2}
+\dreieck{10}{8}
+\dreieck{10}{10}
+
+\dreieck{11}{0}
+\dreieck{11}{1}
+\dreieck{11}{2}
+\dreieck{11}{3}
+\dreieck{11}{8}
+\dreieck{11}{9}
+\dreieck{11}{10}
+\dreieck{11}{11}
+
+\dreieck{12}{0}
+\dreieck{12}{4}
+\dreieck{12}{8}
+\dreieck{12}{12}
+
+\dreieck{13}{0}
+\dreieck{13}{1}
+\dreieck{13}{4}
+\dreieck{13}{5}
+\dreieck{13}{8}
+\dreieck{13}{9}
+\dreieck{13}{12}
+\dreieck{13}{13}
+
+\dreieck{14}{0}
+\dreieck{14}{2}
+\dreieck{14}{4}
+\dreieck{14}{6}
+\dreieck{14}{8}
+\dreieck{14}{10}
+\dreieck{14}{12}
+\dreieck{14}{14}
+
+\dreieck{15}{0}
+\dreieck{15}{1}
+\dreieck{15}{2}
+\dreieck{15}{3}
+\dreieck{15}{4}
+\dreieck{15}{5}
+\dreieck{15}{6}
+\dreieck{15}{7}
+\dreieck{15}{8}
+\dreieck{15}{9}
+\dreieck{15}{10}
+\dreieck{15}{11}
+\dreieck{15}{12}
+\dreieck{15}{13}
+\dreieck{15}{14}
+\dreieck{15}{15}
+
+\dreieck{16}{0}
+\dreieck{16}{16}
+
+\dreieck{17}{0}
+\dreieck{17}{1}
+\dreieck{17}{16}
+\dreieck{17}{17}
+
+\dreieck{18}{0}
+\dreieck{18}{2}
+\dreieck{18}{16}
+\dreieck{18}{18}
+
+\dreieck{19}{0}
+\dreieck{19}{1}
+\dreieck{19}{2}
+\dreieck{19}{3}
+\dreieck{19}{16}
+\dreieck{19}{17}
+\dreieck{19}{18}
+\dreieck{19}{19}
+
+\dreieck{20}{0}
+\dreieck{20}{4}
+\dreieck{20}{16}
+\dreieck{20}{20}
+
+\dreieck{21}{0}
+\dreieck{21}{1}
+\dreieck{21}{4}
+\dreieck{21}{5}
+\dreieck{21}{16}
+\dreieck{21}{17}
+\dreieck{21}{20}
+\dreieck{21}{21}
+
+\dreieck{22}{0}
+\dreieck{22}{2}
+\dreieck{22}{4}
+\dreieck{22}{6}
+\dreieck{22}{16}
+\dreieck{22}{18}
+\dreieck{22}{20}
+\dreieck{22}{22}
+
+\dreieck{23}{0}
+\dreieck{23}{1}
+\dreieck{23}{2}
+\dreieck{23}{3}
+\dreieck{23}{4}
+\dreieck{23}{5}
+\dreieck{23}{6}
+\dreieck{23}{7}
+\dreieck{23}{16}
+\dreieck{23}{17}
+\dreieck{23}{18}
+\dreieck{23}{19}
+\dreieck{23}{20}
+\dreieck{23}{21}
+\dreieck{23}{22}
+\dreieck{23}{23}
+
+\dreieck{24}{0}
+\dreieck{24}{8}
+\dreieck{24}{16}
+\dreieck{24}{24}
+
+\dreieck{25}{0}
+\dreieck{25}{1}
+\dreieck{25}{8}
+\dreieck{25}{9}
+\dreieck{25}{16}
+\dreieck{25}{17}
+\dreieck{25}{24}
+\dreieck{25}{25}
+
+\dreieck{26}{0}
+\dreieck{26}{2}
+\dreieck{26}{8}
+\dreieck{26}{10}
+\dreieck{26}{16}
+\dreieck{26}{18}
+\dreieck{26}{24}
+\dreieck{26}{26}
+
+\dreieck{27}{0}
+\dreieck{27}{1}
+\dreieck{27}{2}
+\dreieck{27}{3}
+\dreieck{27}{8}
+\dreieck{27}{9}
+\dreieck{27}{10}
+\dreieck{27}{11}
+\dreieck{27}{16}
+\dreieck{27}{17}
+\dreieck{27}{18}
+\dreieck{27}{19}
+\dreieck{27}{24}
+\dreieck{27}{25}
+\dreieck{27}{26}
+\dreieck{27}{27}
+
+\dreieck{28}{0}
+\dreieck{28}{4}
+\dreieck{28}{8}
+\dreieck{28}{12}
+\dreieck{28}{16}
+\dreieck{28}{20}
+\dreieck{28}{24}
+\dreieck{28}{28}
+
+\dreieck{29}{0}
+\dreieck{29}{1}
+\dreieck{29}{4}
+\dreieck{29}{5}
+\dreieck{29}{8}
+\dreieck{29}{9}
+\dreieck{29}{12}
+\dreieck{29}{13}
+\dreieck{29}{16}
+\dreieck{29}{17}
+\dreieck{29}{20}
+\dreieck{29}{21}
+\dreieck{29}{24}
+\dreieck{29}{25}
+\dreieck{29}{28}
+\dreieck{29}{29}
+
+\foreach \k in {0,2,...,30}{
+ \dreieck{30}{\k}
+}
+
+\foreach \k in {0,...,31}{
+ \dreieck{31}{\k}
+}
+
+\dreieck{32}{0}
+\dreieck{32}{32}
+
+\def\etikett#1#2#3{
+ \node at ({\xs*(-#1+2*#2)},{-\ys*(#1+0.5)}) {$#3$};
+}
+
+\etikett{0}{-2}{n=0}
+\etikett{2}{-2}{n=2}
+\etikett{4}{-2}{n=4}
+\etikett{8}{-2}{n=8}
+\etikett{16}{-2}{n=16}
+\etikett{32}{-2}{n=32}
+
+\def\exponent#1#2#3{
+ \node at ({\xs*(-#1+2*#2)},{-\ys*(#1+0.5)}) [rotate=60] {$#3$};
+}
+
+\exponent{-2}{0}{k=0}
+\exponent{0}{2}{k=2}
+\exponent{2}{4}{k=4}
+\exponent{6}{8}{k=8}
+\exponent{14}{16}{k=16}
+\exponent{30}{32}{k=32}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/30-endlichekoerper/images/binomial5.pdf b/buch/chapters/30-endlichekoerper/images/binomial5.pdf
new file mode 100644
index 0000000..1b2a813
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/binomial5.pdf
Binary files differ
diff --git a/buch/chapters/30-endlichekoerper/images/binomial5.tex b/buch/chapters/30-endlichekoerper/images/binomial5.tex
new file mode 100644
index 0000000..750b7e0
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/binomial5.tex
@@ -0,0 +1,379 @@
+%
+% binomial2.tex -- Parität der Binomialkoeffizienten
+%
+% (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}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\definecolor{farbe0}{rgb}{1,1,1}
+\input{farben.tex}
+
+\def\s{0.37}
+\pgfmathparse{\s*sqrt(3)/2}
+\xdef\ys{\pgfmathresult}
+\pgfmathparse{\s/2}
+\xdef\xs{\pgfmathresult}
+
+%
+% #1 = n
+% #2 = k
+%
+\def\dreieck#1#2#3{
+ \fill[color=farbe#3] ({\xs*(-#1+2*#2)},{-\ys*#1})
+ -- ({\xs*(-#1+2*#2-1)},{-\ys*(#1+1)})
+ -- ({\xs*(-#1+2*#2+1)},{-\ys*(#1+1)}) -- cycle;
+ \node[color=white] at ( ({\xs*(-#1+2*#2)},{-\ys*(#1+0.5)-0.03}) {$\scriptstyle #3$};
+}
+
+\definecolor{gelb}{rgb}{1,0.8,0.2}
+\def\zeile#1{
+ \fill[color=gelb]
+ ({\xs*(-#1)},{-\ys*#1})
+ -- ({\xs*(-#1-1)},{-\ys*(#1+1)})
+ -- ({\xs*(#1+1)},{-\ys*(#1+1)})
+ -- ({\xs*(#1)},{-\ys*#1}) -- cycle;
+}
+
+\zeile{5}
+\zeile{25}
+
+\dreieck{0}{0}{1}
+
+\dreieck{1}{0}{1}
+\dreieck{1}{1}{1}
+
+\dreieck{2}{0}{1}
+\dreieck{2}{1}{2}
+\dreieck{2}{2}{1}
+
+\dreieck{3}{0}{1}
+\dreieck{3}{1}{3}
+\dreieck{3}{2}{3}
+\dreieck{3}{3}{1}
+
+\dreieck{4}{0}{1}
+\dreieck{4}{1}{4}
+\dreieck{4}{2}{1}
+\dreieck{4}{3}{4}
+\dreieck{4}{4}{1}
+
+\dreieck{5}{0}{1}
+\dreieck{5}{5}{1}
+
+\dreieck{6}{0}{1}
+\dreieck{6}{1}{1}
+\dreieck{6}{5}{1}
+\dreieck{6}{6}{1}
+
+\dreieck{7}{0}{1}
+\dreieck{7}{1}{2}
+\dreieck{7}{2}{1}
+\dreieck{7}{5}{1}
+\dreieck{7}{6}{2}
+\dreieck{7}{7}{1}
+
+\dreieck{8}{0}{1}
+\dreieck{8}{1}{3}
+\dreieck{8}{2}{3}
+\dreieck{8}{3}{1}
+\dreieck{8}{5}{1}
+\dreieck{8}{6}{3}
+\dreieck{8}{7}{3}
+\dreieck{8}{8}{1}
+
+\dreieck{9}{0}{1}
+\dreieck{9}{1}{4}
+\dreieck{9}{2}{1}
+\dreieck{9}{3}{4}
+\dreieck{9}{4}{1}
+\dreieck{9}{5}{1}
+\dreieck{9}{6}{4}
+\dreieck{9}{7}{1}
+\dreieck{9}{8}{4}
+\dreieck{9}{9}{1}
+
+\dreieck{10}{0}{1}
+\dreieck{10}{5}{2}
+\dreieck{10}{10}{1}
+
+\dreieck{11}{0}{1}
+\dreieck{11}{1}{1}
+\dreieck{11}{5}{2}
+\dreieck{11}{6}{2}
+\dreieck{11}{10}{1}
+\dreieck{11}{11}{1}
+
+\dreieck{12}{0}{1}
+\dreieck{12}{1}{2}
+\dreieck{12}{2}{1}
+\dreieck{12}{5}{2}
+\dreieck{12}{6}{4}
+\dreieck{12}{7}{2}
+\dreieck{12}{10}{1}
+\dreieck{12}{11}{2}
+\dreieck{12}{12}{1}
+
+\dreieck{13}{0}{1}
+\dreieck{13}{1}{3}
+\dreieck{13}{2}{3}
+\dreieck{13}{3}{1}
+\dreieck{13}{5}{2}
+\dreieck{13}{6}{1}
+\dreieck{13}{7}{1}
+\dreieck{13}{8}{2}
+\dreieck{13}{10}{1}
+\dreieck{13}{11}{3}
+\dreieck{13}{12}{3}
+\dreieck{13}{13}{1}
+
+\dreieck{14}{0}{1}
+\dreieck{14}{1}{4}
+\dreieck{14}{2}{1}
+\dreieck{14}{3}{4}
+\dreieck{14}{4}{1}
+\dreieck{14}{5}{2}
+\dreieck{14}{6}{3}
+\dreieck{14}{7}{2}
+\dreieck{14}{8}{3}
+\dreieck{14}{9}{2}
+\dreieck{14}{10}{1}
+\dreieck{14}{11}{4}
+\dreieck{14}{12}{1}
+\dreieck{14}{13}{4}
+\dreieck{14}{14}{1}
+
+\dreieck{15}{0}{1}
+\dreieck{15}{5}{3}
+\dreieck{15}{10}{3}
+\dreieck{15}{15}{1}
+
+\dreieck{16}{0}{1}
+\dreieck{16}{1}{1}
+\dreieck{16}{5}{3}
+\dreieck{16}{6}{3}
+\dreieck{16}{10}{3}
+\dreieck{16}{11}{3}
+\dreieck{16}{15}{1}
+\dreieck{16}{16}{3}
+
+\dreieck{17}{0}{1}
+\dreieck{17}{1}{2}
+\dreieck{17}{2}{1}
+\dreieck{17}{5}{3}
+\dreieck{17}{6}{1}
+\dreieck{17}{7}{3}
+\dreieck{17}{10}{3}
+\dreieck{17}{11}{1}
+\dreieck{17}{12}{3}
+\dreieck{17}{15}{1}
+\dreieck{17}{16}{2}
+\dreieck{17}{17}{1}
+
+\dreieck{18}{0}{1}
+\dreieck{18}{1}{3}
+\dreieck{18}{2}{3}
+\dreieck{18}{3}{1}
+\dreieck{18}{5}{3}
+\dreieck{18}{6}{4}
+\dreieck{18}{7}{4}
+\dreieck{18}{8}{3}
+\dreieck{18}{10}{3}
+\dreieck{18}{11}{4}
+\dreieck{18}{12}{4}
+\dreieck{18}{13}{3}
+\dreieck{18}{15}{1}
+\dreieck{18}{16}{3}
+\dreieck{18}{17}{3}
+\dreieck{18}{18}{1}
+
+\dreieck{19}{0}{1}
+\dreieck{19}{1}{4}
+\dreieck{19}{2}{1}
+\dreieck{19}{3}{4}
+\dreieck{19}{4}{1}
+\dreieck{19}{5}{3}
+\dreieck{19}{6}{2}
+\dreieck{19}{7}{3}
+\dreieck{19}{8}{2}
+\dreieck{19}{9}{3}
+\dreieck{19}{10}{3}
+\dreieck{19}{11}{2}
+\dreieck{19}{12}{3}
+\dreieck{19}{13}{2}
+\dreieck{19}{14}{3}
+\dreieck{19}{15}{1}
+\dreieck{19}{16}{4}
+\dreieck{19}{17}{1}
+\dreieck{19}{18}{4}
+\dreieck{19}{19}{1}
+
+\dreieck{20}{0}{1}
+\dreieck{20}{5}{4}
+\dreieck{20}{10}{1}
+\dreieck{20}{15}{4}
+\dreieck{20}{20}{1}
+
+\dreieck{21}{0}{1}
+\dreieck{21}{1}{1}
+\dreieck{21}{5}{4}
+\dreieck{21}{6}{4}
+\dreieck{21}{10}{1}
+\dreieck{21}{11}{1}
+\dreieck{21}{15}{4}
+\dreieck{21}{16}{4}
+\dreieck{21}{20}{1}
+\dreieck{21}{21}{1}
+
+\dreieck{22}{0}{1}
+\dreieck{22}{1}{2}
+\dreieck{22}{2}{1}
+\dreieck{22}{5}{4}
+\dreieck{22}{6}{3}
+\dreieck{22}{7}{4}
+\dreieck{22}{10}{1}
+\dreieck{22}{11}{2}
+\dreieck{22}{12}{1}
+\dreieck{22}{15}{4}
+\dreieck{22}{16}{3}
+\dreieck{22}{17}{4}
+\dreieck{22}{20}{1}
+\dreieck{22}{21}{2}
+\dreieck{22}{22}{1}
+
+\dreieck{23}{0}{1}
+\dreieck{23}{1}{3}
+\dreieck{23}{2}{3}
+\dreieck{23}{3}{1}
+\dreieck{23}{5}{4}
+\dreieck{23}{6}{2}
+\dreieck{23}{7}{2}
+\dreieck{23}{8}{4}
+\dreieck{23}{10}{1}
+\dreieck{23}{11}{3}
+\dreieck{23}{12}{3}
+\dreieck{23}{13}{1}
+\dreieck{23}{15}{4}
+\dreieck{23}{16}{2}
+\dreieck{23}{17}{2}
+\dreieck{23}{18}{4}
+\dreieck{23}{20}{1}
+\dreieck{23}{21}{3}
+\dreieck{23}{22}{3}
+\dreieck{23}{23}{1}
+
+\dreieck{24}{0}{1}
+\dreieck{24}{1}{4}
+\dreieck{24}{2}{1}
+\dreieck{24}{3}{4}
+\dreieck{24}{4}{1}
+\dreieck{24}{5}{4}
+\dreieck{24}{6}{1}
+\dreieck{24}{7}{4}
+\dreieck{24}{8}{1}
+\dreieck{24}{9}{4}
+\dreieck{24}{10}{1}
+\dreieck{24}{11}{4}
+\dreieck{24}{12}{1}
+\dreieck{24}{13}{4}
+\dreieck{24}{14}{1}
+\dreieck{24}{15}{4}
+\dreieck{24}{16}{1}
+\dreieck{24}{17}{4}
+\dreieck{24}{18}{1}
+\dreieck{24}{19}{4}
+\dreieck{24}{20}{1}
+\dreieck{24}{21}{4}
+\dreieck{24}{22}{1}
+\dreieck{24}{23}{4}
+\dreieck{24}{24}{1}
+
+\dreieck{25}{0}{1}
+\dreieck{25}{25}{1}
+
+\dreieck{26}{0}{1}
+\dreieck{26}{1}{1}
+\dreieck{26}{25}{1}
+\dreieck{26}{26}{1}
+
+\dreieck{27}{0}{1}
+\dreieck{27}{1}{2}
+\dreieck{27}{2}{1}
+\dreieck{27}{25}{1}
+\dreieck{27}{26}{2}
+\dreieck{27}{27}{1}
+
+\dreieck{28}{0}{1}
+\dreieck{28}{1}{3}
+\dreieck{28}{2}{3}
+\dreieck{28}{3}{1}
+\dreieck{28}{25}{1}
+\dreieck{28}{26}{3}
+\dreieck{28}{27}{3}
+\dreieck{28}{28}{1}
+
+\dreieck{29}{0}{1}
+\dreieck{29}{1}{4}
+\dreieck{29}{2}{1}
+\dreieck{29}{3}{4}
+\dreieck{29}{4}{1}
+\dreieck{29}{25}{1}
+\dreieck{29}{26}{4}
+\dreieck{29}{27}{1}
+\dreieck{29}{28}{4}
+\dreieck{29}{29}{1}
+
+\dreieck{30}{0}{1}
+\dreieck{30}{5}{1}
+\dreieck{30}{25}{1}
+\dreieck{30}{30}{1}
+
+\dreieck{31}{0}{1}
+\dreieck{31}{1}{1}
+\dreieck{31}{5}{1}
+\dreieck{31}{6}{1}
+\dreieck{31}{25}{1}
+\dreieck{31}{26}{1}
+\dreieck{31}{30}{1}
+\dreieck{31}{31}{1}
+
+\dreieck{32}{0}{1}
+\dreieck{32}{1}{2}
+\dreieck{32}{2}{1}
+\dreieck{32}{5}{1}
+\dreieck{32}{6}{2}
+\dreieck{32}{7}{1}
+\dreieck{32}{25}{1}
+\dreieck{32}{26}{2}
+\dreieck{32}{27}{1}
+\dreieck{32}{30}{1}
+\dreieck{32}{31}{2}
+\dreieck{32}{32}{1}
+
+\def\etikett#1#2#3{
+ \node at ({\xs*(-#1+2*#2)},{-\ys*(#1+0.5)}) {$#3$};
+}
+
+\etikett{0}{-2}{n=0}
+\etikett{5}{-2}{n=5}
+\etikett{25}{-2}{n=25}
+
+\def\exponent#1#2#3{
+ \node at ({\xs*(-#1+2*#2)},{-\ys*(#1+0.5)}) [rotate=60] {$#3$};
+}
+
+\exponent{-2}{0}{k=0}
+\exponent{3}{5}{k=5}
+\exponent{23}{25}{k=25}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/30-endlichekoerper/images/farben.tex b/buch/chapters/30-endlichekoerper/images/farben.tex
new file mode 100644
index 0000000..553bb91
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/farben.tex
@@ -0,0 +1,4 @@
+\definecolor{farbe1}{rgb}{0,0,0}
+\definecolor{farbe2}{rgb}{1,0,0}
+\definecolor{farbe3}{rgb}{0,0.6,0}
+\definecolor{farbe4}{rgb}{0,0,1}
diff --git a/buch/chapters/30-endlichekoerper/rechnungen/euinv.maxima b/buch/chapters/30-endlichekoerper/rechnungen/euinv.maxima
new file mode 100644
index 0000000..ce5b7f2
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/rechnungen/euinv.maxima
@@ -0,0 +1,31 @@
+m: X^3 +2*X^2 + 2*X + 3;
+f: 2*X^2 + 2*X + 1;
+
+q0: 4*X+4;
+r0: 4*X+6;
+expand(q0*f+r0);
+
+q1: 4*X+5;
+r1: 6;
+expand(q1*r0+r1);
+
+q2: 3*X+1;
+r2: 0;
+expand(q2*r1+r2);
+
+Q0: matrix([ 0, 1 ], [ 1, (7*X+7)-q0 ]);
+Q1: matrix([ 0, 1 ], [ 1, (7*X+7)-q1 ]);
+Q2: matrix([ 0, 1 ], [ 1, (7*X+7)-q2 ]);
+
+Q: expand(Q1 . Q0);
+s: Q[1,1];
+t: Q[1,2];
+expand(s*m+t*f);
+
+Q: expand(Q2 . Q);
+
+s: Q[1,1];
+t: Q[1,2];
+
+expand(s*m+t*f);
+
diff --git a/buch/chapters/30-endlichekoerper/rechnungen/invbeispiel.maxima b/buch/chapters/30-endlichekoerper/rechnungen/invbeispiel.maxima
new file mode 100644
index 0000000..f227f3a
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/rechnungen/invbeispiel.maxima
@@ -0,0 +1,81 @@
+/*
+ * invbeispiel.maxima
+ *
+ * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+ */
+
+m: X^3 + 2*X^2 + 2*X + 3;
+
+modulus:7;
+factor(m);
+modulus:false;
+
+M: matrix(
+ [ 0, 0, -3 ],
+ [ 1, 0, -2 ],
+ [ 0, 1, -2 ]
+);
+M: mod(M, 7);
+M0: identfor(M);
+M1: M;
+M2: M.M1;
+
+a0: 1;
+a1: 2;
+a2: 2;
+
+a: a0 + a1*X + a2*X^2;
+
+A: a0*M0 + a1*M1 + a2*M2;
+A: mod(A, 7);
+
+T: matrix(
+ [ A[1,1], A[1,2], A[1,3], 1, 0, 0 ],
+ [ A[2,1], A[2,2], A[2,3], 0, 1, 0 ],
+ [ A[3,1], A[3,2], A[3,3], 0, 0, 1 ]
+);
+
+t: inv_mod(T[1,1], 7);
+T[1]: mod(t * T[1], 7);
+T[2]: mod(T[2] - T[2,1]*T[1], 7);
+T[3]: mod(T[3] - T[3,1]*T[1], 7);
+T;
+
+t: inv_mod(T[2,2], 7);
+T[2]: mod(t * T[2], 7);
+T[3]: mod(T[3] - T[3,2] * T[2], 7);
+T;
+
+t: inv_mod(T[3,3], 7);
+T[3]: mod(t * T[3], 7);
+T;
+
+T[2]: mod(T[2] - T[2,3] * T[3], 7);
+T[1]: mod(T[1] - T[1,3] * T[3], 7);
+T;
+
+T[1]: mod(T[1] - T[1,2] * T[2], 7);
+T;
+
+C: matrix(
+ [ T[1,4], T[1,5], T[1,6] ],
+ [ T[2,4], T[2,5], T[2,6] ],
+ [ T[3,4], T[3,5], T[3,6] ]
+);
+
+mod(A.C, 7);
+
+b0: C[1,1];
+b1: C[2,1];
+b2: C[3,1];
+
+Cc: mod(b0*M0 + b1*M1 + b2*M2, 7);
+C - Cc;
+
+b: b0 + b1*X + b2*X^2;
+p: expand(a*b);
+
+pp: 3*X^4 + X^3 + 3*X^2 + 6*X;
+
+divide(pp, m, X);
+
diff --git a/buch/chapters/30-endlichekoerper/rechnungen/inverse.maxima b/buch/chapters/30-endlichekoerper/rechnungen/inverse.maxima
new file mode 100644
index 0000000..5f3682f
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/rechnungen/inverse.maxima
@@ -0,0 +1,35 @@
+/*
+ * inverse.maxima
+ *
+ * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+ */
+n: 5;
+m: X^5 + 15*X^3 - 30*X^2 + 45;
+
+M: matrix(
+ [ 0, 0, 0, 0, -45 ],
+ [ 1, 0, 0, 0, 0 ],
+ [ 0, 1, 0, 0, 30 ],
+ [ 0, 0, 1, 0, -15 ],
+ [ 0, 0, 0, 1, 0 ]
+);
+M2: M.M;
+M3: M.M2;
+M4: M.M3;
+
+y: a0 + a1*X + a2*X^2 + a3*X^3 + a4*X^4;
+Y: a0*identfor(M) + a1*M + a2*M2 + a3*M3 + a4*M4;
+
+B: invert(Y);
+
+b0: B[1,1];
+b1: B[2,1];
+b2: B[3,1];
+b3: B[4,1];
+b4: B[5,1];
+
+Z: b0*identfor(M) + b1*M + b2*M2 + b3*M3 + b4*M4;
+z: b0 + b1*X + b2*X^2 + b3*X^3 + b4*X^4;
+
+w: expand(y*z);
+remainder(w, m, X);
diff --git a/buch/chapters/30-endlichekoerper/rechnungen/multiplikation.maxima b/buch/chapters/30-endlichekoerper/rechnungen/multiplikation.maxima
new file mode 100644
index 0000000..e09f848
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/rechnungen/multiplikation.maxima
@@ -0,0 +1,38 @@
+/*
+ * multiplikation.maxima
+ *
+ * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+ */
+
+Malpha: matrix(
+[ 0, 0, 0, 0, 0, 0, -m0 ],
+[ 1, 0, 0, 0, 0, 0, -m1 ],
+[ 0, 1, 0, 0, 0, 0, -m2 ],
+[ 0, 0, 1, 0, 0, 0, -m3 ],
+[ 0, 0, 0, 1, 0, 0, -m4 ],
+[ 0, 0, 0, 0, 1, 0, -m5 ],
+[ 0, 0, 0, 0, 0, 1, -m6 ]
+);
+
+Malpha2: expand(Malpha . Malpha);
+Malpha3: expand(Malpha . Malpha2);
+Malpha4: expand(Malpha . Malpha3);
+Malpha5: expand(Malpha . Malpha4);
+Malpha6: expand(Malpha . Malpha5);
+Malpha7: expand(Malpha . Malpha6);
+Malpha8: expand(Malpha . Malpha7);
+
+p: m0 * identfor(Malpha)
++ m1 * Malpha
++ m2 * Malpha2
++ m3 * Malpha3
++ m4 * Malpha4
++ m5 * Malpha5
++ m6 * Malpha6
++ Malpha7;
+expand(p);
+
+
+m(X) := m0 + m1*X + m2*X^2 + m3*X^3 + m4*X^4 + m5*X^5 + m6*X^6 + X^7;
+
+invert(Malpha);
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex
new file mode 100644
index 0000000..4f4d56d
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3001.tex
@@ -0,0 +1,102 @@
+Im Rahmen der Aufgabe, die Zehntausenderstelle der Zahl $5^{5^{5^{5^5}}}$
+zu berechnen muss Michael Penn im Video
+\url{https://youtu.be/Xg24FinMiws} bei 12:52 zwei Zahlen $x$ und $y$ finden,
+so dass,
+\[
+5^5x
++
+2^5y
+=
+1
+\]
+ist.
+Verwenden Sie die Matrixform des euklidischen Algorithmus.
+
+\begin{loesung}
+Zunächst berechnen wir die beiden Potenzen
+\[
+5^5 = 3125
+\qquad\text{und}\qquad
+2^5 = 32.
+\]
+Damit können wir jetzt den Algorithmus durchführen.
+Die Quotienten und Reste sind
+\begin{align*}
+a_0&=q_0\cdot b_0 + r_0&
+3125 &= 97 \cdot 32 + 21& q_0&=97 & r_0&= 21\\
+a_1&=q_1\cdot b_1 + r_1&
+32 &= 1\cdot 21 + 10 & q_1&= 1 & r_1&= 11\\
+a_2&=q_2\cdot b_2 + r_2&
+21 &= 1\cdot 11 + 10 & q_2&= 1 & r_2&= 10\\
+a_3&=q_3\cdot b_3 + r_3&
+11 &= 1\cdot 10 + 1 & q_3&= 1 & r_3&= 1\\
+a_4&=q_4\cdot b_4 + r_4&
+10 &= 10\cdot 1 + 0 & q_4&=10 & r_4&= 0
+\end{align*}
+Daraus kann man jetzt auch die Matrizen $Q(q_k)$ bestimmen und
+ausmultiplizieren:
+\begin{align*}
+Q
+&=
+\begin{pmatrix}
+0&1\\1&-10
+\end{pmatrix}
+\underbrace{
+\begin{pmatrix}
+0&1\\1&-1
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\1&-1
+\end{pmatrix}
+}_{}
+\underbrace{
+\begin{pmatrix}
+0&1\\1&-1
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\1&-97
+\end{pmatrix}
+}_{}
+\\
+&=
+\begin{pmatrix}
+0&1\\1&-10
+\end{pmatrix}
+\underbrace{
+\begin{pmatrix}
+0&-1\\-1&2
+\end{pmatrix}
+\begin{pmatrix}
+1&-97\\-1&98
+\end{pmatrix}
+}_{}
+\\
+&=
+\underbrace{
+\begin{pmatrix}
+0&1\\1&-10
+\end{pmatrix}
+\begin{pmatrix}
+2&-195\\-3&293
+\end{pmatrix}
+}_{}
+\\
+&=
+\begin{pmatrix}
+-3&293\\32&-3125
+\end{pmatrix}.
+\end{align*}
+Daras kann man jetzt ablesen, dass
+\[
+-3\cdot 3125
++
+293\cdot 32
+=
+-9375
++
+9376
+=
+1.
+\]
+Die gesuchten Zahlen sind also $x=-3$ und $y=293$.
+\end{loesung}
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex
new file mode 100644
index 0000000..63200a7
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3002.tex
@@ -0,0 +1,9 @@
+Berechnen Sie $666^{666}$ in $\mathbb{F}_{13}$.
+
+\begin{loesung}
+Zunächst ist die Basis der Potenz $666=3$ in $\mathbb{F}_{13}$, es
+muss also nur $3^{666}$ berechnet werden.
+Nach dem kleinen Satz von Fermat ist $3^{12}=1$ in $\mathbb{F}_{13}$.
+Wegen $666 = 12\cdot 50+6$ folgt
+$ 3^{666} = 3^6=729=1$ in $\mathbb{F}_{13}$.
+\end{loesung}
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex
new file mode 100644
index 0000000..8a83256
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3003.tex
@@ -0,0 +1,72 @@
+Die Zahl $p=47$ ist eine Primzahl, der Ring
+$\mathbb{Z}/p\mathbb{Z}=\mathbb{F}_{47}$ ist daher ein Körper.
+Jeder von Null verschiedene Rest $b\in\mathbb{F}_p^*$ hat daher eine
+multiplikative Inverse.
+Berechnen Sie die multiplikative Inverse von $b=11\in\mathbb{F}_{47}$.
+
+\begin{loesung}
+Der euklidische Algorithmus muss auf die Zahlen $p=47$ und $b=11$ angewendet
+werden, es ergeben sich die Quotienten und Reste der folgenden Tabelle:
+\begin{center}
+\begin{tabular}{|>{$}c<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
+\hline
+k&a_k&b_k&q_k&r_k\\
+\hline
+0& 47& 11& 4& 3\\
+1& 11& 3& 3& 2\\
+2& 3& 2& 1& 1\\
+3& 2& 1& 2& 0\\
+\hline
+\end{tabular}
+\end{center}
+Wie erwartet ist der grösste gemeinsame Teiler
+$\operatorname{ggT}(47,11)=r_2=1$.
+Um die Zahlen $s,t$ zu finden, für die $sp+tb=1$ gilt, können wir die
+Matrixform verwenden, wir berechnen dazu
+\begin{align*}
+Q
+=
+Q(2)Q(1)Q(3)Q(4)
+&=
+\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
+\begin{pmatrix} 0&1\\1&-1 \end{pmatrix}
+\begin{pmatrix} 0&1\\1&-3 \end{pmatrix}
+\begin{pmatrix} 0&1\\1&-4 \end{pmatrix}
+\\
+&=
+\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
+\begin{pmatrix} 0&1\\1&-1 \end{pmatrix}
+\begin{pmatrix} 1&-4\\-3&13\end{pmatrix}
+\\
+&=
+\begin{pmatrix} 0&1\\1&-2 \end{pmatrix}
+\begin{pmatrix} -3&13\\4&-17 \end{pmatrix}
+\\
+&=
+\begin{pmatrix} 4&-17\\ -11&47 \end{pmatrix}.
+\end{align*}
+Daraus kann man ablesen, dass $s=4$ und $t=-17$, tatsächlich ist
+$4\cdot 47-47\cdot 11=188-187=1$.
+Wir schliessen daraus, dass $-17=30\in\mathbb{F}_{47}$ die multiplikative
+Inverse von $b=11$ ist.
+Die Rechnung $11\cdot 30 = 330 = 7\cdot 47 + 1$ zeigt, dass dies
+der Fall ist.
+
+Alternativ zur Matrixdarstellung kann man die Koeffizienten $s$ und $t$
+auch mit Hilfe der erweiterten Tabelle finden:
+\begin{center}
+\begin{tabular}{|>{$}c<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
+\hline
+k&a_k&b_k&q_k&r_k&c_k&d_k\\
+\hline
+ & & & & & 1& 0\\
+0& 47& 11& 4& 3& 0& 1\\
+1& 11& 3& 3& 2& 1& -4\\
+2& 3& 2& 1& 1& -3& 13\\
+3& 2& 1& 2& 0& {\color{red}4}&{\color{red}-17}\\
+4& 1& 0& & &-11& 47\\
+\hline
+\end{tabular}
+\end{center}
+Die gesuchten Zahlen $s$ und $t$ sind rot hervorgehoben.
+\end{loesung}
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex
new file mode 100644
index 0000000..046ac94
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004.tex
@@ -0,0 +1,234 @@
+Der Körper $\mathbb{F}_2$ ist besonders einfach, da er nur zwei Elemente
+$0$ und $1$ enthält.
+\begin{teilaufgaben}
+\item
+Bestimmen Sie die Additions- und Multiplikationstabelle für $\mathbb{F}_2$.
+\item
+Lösen Sie das lineare Gleichungssystem
+\[
+\begin{linsys}{4}
+x_1&+& x_2& & & & &=& 0\\
+ & & x_2&+&x_3&+&x_4&=& 1\\
+x_1&+& x_2&+&x_3&+&x_4&=& 1\\
+ & & x_2&+&x_3& & &=& 0\\
+\end{linsys}
+\]
+über dem Körper $\mathbb{F}_2$ mit dem Gauss-Algorithmus.
+\item Bestimmen Sie die Inverse $A^{-1}\in \operatorname{GL}_2(\mathbb{F}_2)$
+der Koeffizientenmatrix $A$ des Gleichungssystems.
+\item Kontrollieren Sie das Resultat durch Ausmultiplizieren des Produktes
+$AA^{-1}$.
+\end{teilaufgaben}
+
+\begin{loesung}
+\begin{teilaufgaben}
+\item
+Die Additions- und Multiplikationstabellen sind
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\def\ds{0.5}
+\def\punkt#1#2{({(#1)*\ds},{(-#2)*\ds})}
+\def\tabelle{
+ \foreach \x in {-0.5,0.5,2.5}{
+ \draw \punkt{\x}{-0.5} -- \punkt{\x}{2.5};
+ }
+ \foreach \y in {-0.5,0.5,2.5}{
+ \draw \punkt{-0.5}{\y} -- \punkt{2.5}{\y};
+ }
+ \node at \punkt{1}{0} {$0$};
+ \node at \punkt{2}{0} {$1$};
+ \node at \punkt{0}{1} {$0$};
+ \node at \punkt{0}{2} {$0$};
+}
+\begin{scope}[xshift=-2cm]
+ \tabelle
+ \node at (0,0) {$+$};
+ \node at \punkt{1}{1} {$0$};
+ \node at \punkt{2}{1} {$1$};
+ \node at \punkt{1}{2} {$1$};
+ \node at \punkt{2}{2} {$0$};
+\end{scope}
+\begin{scope}[xshift=2cm]
+ \tabelle
+ \node at (0,0) {$\cdot$};
+ \node at \punkt{1}{1} {$0$};
+ \node at \punkt{2}{1} {$0$};
+ \node at \punkt{1}{2} {$0$};
+ \node at \punkt{2}{2} {$1$};
+\end{scope}
+\end{tikzpicture}
+\end{center}
+Betrachtet als Bitoperationen entspricht die Addition dem XOR, die
+Multiplikation dem AND.
+\item
+Die Gauss-Tableaux sind
+\begin{align*}
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+ 1 & 1 & 0 & 0 & 1\\
+ 0 & 1 & 1 & 1 & 0\\
+ 1 & 1 & 1 & 1 & 0\\
+ 0 & 1 & 1 & 0 & 1\\
+\hline
+\end{tabular}
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+ 1 & 1 & 0 & 0 & 1\\
+ 0 & 1 & 1 & 1 & 0\\
+ 0 & 0 & 1 & 1 & 1\\
+ 0 & 1 & 1 & 0 & 1\\
+\hline
+\end{tabular}
+%\\
+%&
+\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+ 1 & 1 & 0 & 0 & 1\\
+ 0 & 1 & 1 & 1 & 0\\
+ 0 & 0 & 1 & 1 & 1\\
+ 0 & 0 & 0 & 1 & 1\\
+\hline
+\end{tabular}
+\\
+\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+ 1 & 1 & 0 & 0 & 1\\
+ 0 & 1 & 1 & 0 & 1\\
+ 0 & 0 & 1 & 0 & 0\\
+ 0 & 0 & 0 & 1 & 1\\
+\hline
+\end{tabular}
+%\\
+&
+\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+ 1 & 1 & 0 & 0 & 1\\
+ 0 & 1 & 0 & 0 & 1\\
+ 0 & 0 & 1 & 0 & 0\\
+ 0 & 0 & 0 & 1 & 1\\
+\hline
+\end{tabular}
+%\\
+%&
+\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|}
+\hline
+ 1 & 0 & 0 & 0 & 0\\
+ 0 & 1 & 0 & 0 & 1\\
+ 0 & 0 & 1 & 0 & 0\\
+ 0 & 0 & 0 & 1 & 1\\
+\hline
+\end{tabular}
+\end{align*}
+In der ersten Zeile stehen die Schritt der Vorwärtsreduktion, in der
+zweiten die Schritte des Rückwärtseinsetzens.
+Als Lösung liest man ab
+\[
+x=\begin{pmatrix}0\\1\\0\\1 \end{pmatrix},
+\]
+die Korrektheit kann man leicht durch Einsetzen überprüfen.
+\item
+Wir wenden erneut den Gauss-Algorithmus an:
+\begin{align*}
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
+ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\
+ 1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\
+ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
+\hline
+\end{tabular}
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
+ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\
+ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\
+ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
+\hline
+\end{tabular}
+\\
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
+ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\
+ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\
+ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
+\hline
+\end{tabular}
+\\
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
+ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
+ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\
+ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
+\hline
+\end{tabular}
+\\
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
+ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\
+ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\
+ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
+\hline
+\end{tabular}
+\\
+&\to
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\
+ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\
+ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\
+ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
+\hline
+\end{tabular}
+\end{align*}
+Daraus liest man die Inverse $A^{-1}$ der Koeffizientenmatrix $A$ ab als
+\[
+A^{-1}
+=
+\begin{pmatrix}
+ 0 & 1 & 1 & 0 \\
+ 1 & 1 & 1 & 0 \\
+ 1 & 1 & 1 & 1 \\
+ 0 & 1 & 0 & 1
+\end{pmatrix}
+\]
+\item Wir prüfen das Resultat durch Ausmultiplizieren:
+\[
+AA^{-1}
+=
+\begin{pmatrix}
+ 1 & 1 & 0 & 0 \\
+ 0 & 1 & 1 & 1 \\
+ 1 & 1 & 1 & 1 \\
+ 0 & 1 & 1 & 0
+\end{pmatrix}
+\begin{pmatrix}
+ 0 & 1 & 1 & 0 \\
+ 1 & 1 & 1 & 0 \\
+ 1 & 1 & 1 & 1 \\
+ 0 & 1 & 0 & 1
+\end{pmatrix}
+=
+\begin{pmatrix}
+ 1 & 0 & 0 & 0 \\
+ 0 & 1 & 0 & 0 \\
+ 0 & 0 & 1 & 0 \\
+ 0 & 0 & 0 & 1
+\end{pmatrix}
+\]
+Dabei kann man verwenden, dass der Eintrag in Zeile $i$ und Spalte $k$ des
+Produktes die Anzahl der Positionen ist, wo in der Zeile $i$ von $A$
+und in der Spalte $j$ von $A^{-1}$ eine $1$ steht.
+\end{teilaufgaben}
+\end{loesung}
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m
new file mode 100644
index 0000000..42e9d9f
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3004/matrix.m
@@ -0,0 +1,22 @@
+#
+# matrix.m
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+
+n = 4
+N = 20;
+p = 2;
+
+d = 0;
+while d == 0
+ A = round(N * rand(n,n));
+ B = mod(A, p);
+ d = det(B);
+ d = mod(d, p);
+ d = d * B(1,1);
+end
+A
+det(A)
+B
+det(B)
diff --git a/buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex
new file mode 100644
index 0000000..28f4d2c
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/uebungsaufgaben/3005.tex
@@ -0,0 +1,205 @@
+Das Polynom $m(X)=X^2+X+1$ ist als Polynom in $\mathbb{F}_3[X]$ irreduzibel.
+Dies bedeutet, dass der Ring der Polynome $\mathbb{F}_3[X] / (m(X))$
+ein Körper ist, man bezeichnet ihn auch mit $\mathbb{F}_3(\alpha)$,
+wobei man sich $\alpha$ als eine Nullstelle von $m(X)$
+oder als die Matrix
+\[
+\alpha = \begin{pmatrix} 0&2\\1&2\end{pmatrix}
+\]
+vorstellen kann.
+\begin{teilaufgaben}
+\item
+Stellen Sie die Additions- und Multiplikationstabellen für das Rechnen
+in $\mathbb{F}_3$ auf.
+\item
+Berechnen Sie $\alpha^{-1}$ in $\mathbb{F}_3(\alpha)$ aus der
+Bedingung $m(\alpha)=0$.
+\item
+Verwenden Sie den euklidischen Algorithmus, um $(1+\alpha)^{-1}$
+in $\mathbb{F}_3(\alpha)$ zu bestimmen.
+\item
+Berechnen Sie $\alpha^3$.
+\end{teilaufgaben}
+
+\begin{loesung}
+\begin{teilaufgaben}
+\item
+Die Additions- und Multiplikationstabelle von $\mathbb{F}_3$ ist
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\def\ds{0.5}
+\def\punkt#1#2{({(#1)*\ds},{-(#2)*\ds})}
+\def\tabelle{
+\foreach \x in {-0.5,0.5,3.5}{
+ \draw \punkt{\x}{-0.5} -- \punkt{\x}{3.5};
+ \draw \punkt{-0.5}{\x} -- \punkt{3.5}{\x};
+}
+\node at \punkt{0}{1} {$0$};
+\node at \punkt{0}{2} {$1$};
+\node at \punkt{0}{3} {$2$};
+\node at \punkt{1}{0} {$0$};
+\node at \punkt{2}{0} {$1$};
+\node at \punkt{3}{0} {$2$};
+}
+\begin{scope}[xshift=-2cm]
+\tabelle
+\node at \punkt{0}{0} {$+$};
+\node at \punkt{1}{1} {$0$};
+\node at \punkt{1}{2} {$1$};
+\node at \punkt{1}{3} {$2$};
+\node at \punkt{2}{1} {$1$};
+\node at \punkt{2}{2} {$2$};
+\node at \punkt{2}{3} {$0$};
+\node at \punkt{3}{1} {$2$};
+\node at \punkt{3}{2} {$0$};
+\node at \punkt{3}{3} {$1$};
+\end{scope}
+\begin{scope}[xshift=2cm]
+\tabelle
+\node at \punkt{0}{0} {$\cdot$};
+\node at \punkt{1}{1} {$0$};
+\node at \punkt{1}{2} {$0$};
+\node at \punkt{1}{3} {$0$};
+\node at \punkt{2}{1} {$0$};
+\node at \punkt{2}{2} {$1$};
+\node at \punkt{2}{3} {$2$};
+\node at \punkt{3}{1} {$0$};
+\node at \punkt{3}{2} {$2$};
+\node at \punkt{3}{3} {$1$};
+\end{scope}
+\end{tikzpicture}
+\end{center}
+\item
+Wegen $m(\alpha)=\alpha^2+\alpha+1=0$ folgt $\alpha+1+\alpha^{-1}=0$
+oder $\alpha^{-1} = -\alpha - 1 = 2+2\alpha$.
+Als Matrix kann man
+\[
+\alpha^{-1}
+=
+2\alpha + 2
+=
+\begin{pmatrix}
+0&4\\
+2&4
+\end{pmatrix}
++
+\begin{pmatrix}
+2&0\\0&2
+\end{pmatrix}
+=
+\begin{pmatrix}
+2&4\\2&2
+\end{pmatrix}
+\equiv
+\begin{pmatrix}2&1\\2&0\end{pmatrix}
+\mod 3
+\]
+schreiben und durch Nachrechnen verifizieren dass, tatsächlich gilt
+\[
+\alpha\alpha^{-1}
+=
+\begin{pmatrix}
+0&2\\
+1&2
+\end{pmatrix}
+\begin{pmatrix}
+2&1\\
+2&0
+\end{pmatrix}
+=
+\begin{pmatrix}
+4&0\\
+6&1
+\end{pmatrix}
+\equiv
+\begin{pmatrix}
+1&0\\
+0&1
+\end{pmatrix}
+\mod 3.
+\]
+\item
+Für den euklidischen Algorithmus müssen wir wiederholt eine Polynomdivision
+in $\mathbb{F}_3[X]$ durchführen.
+Im ersten Schritt ist es
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcr}
+ \llap{$($}X^2&+&X&+&1\rlap{$)$}&\;:&(X&+&1)&=&X = q_1\\
+\llap{$-($}X^2&+&X\rlap{$)$}& & & & & & & & \\ \cline{1-3}
+ & &0&+&1 &\rlap{$\mathstrut = r_1$}\phantom{)}& & & & & \\
+\end{array}
+\]
+Die nächste Division ist $(X+1) : 1$, die als Quotient $q_2=X+1$ und den
+Rest $r_2=0$ hat.
+Mit der Matrixform des euklidischen Algorithmus kann man jetzt auch die
+Koeffizienten $s$ und $t$ bestimmen, die beide Polynome in $\mathbb{F}_3[X]$
+sind:
+\begin{align*}
+Q
+&=
+Q(q_2)
+Q(q_1)
+=
+\begin{pmatrix}
+0&1\\1&-q_2
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\1&-q_1
+\end{pmatrix}
+=
+\begin{pmatrix}
+0&1\\1&2X+2
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\{\color{red}1}&{\color{red}2X}
+\end{pmatrix}
+=
+\begin{pmatrix}
+{\color{red}1}&{\color{red}2X}\\
+2X&X^2+X+1
+\end{pmatrix}.
+\end{align*}
+Die gesuchten Polynome sind $s=1$ und $t=2X$ und man kann nachrechnen,
+dass
+\begin{align*}
+s\cdot m(X) + t\cdot (X+1)
+&=
+X^2+X+1 + 2X\cdot (X+1)
+=
+X^2+X+1 + 2X^2 + 2X
+\\
+&= 3X^2+3X+1\equiv 1 \mod 3.
+\end{align*}
+Natürlich kann man $s$ und $t$ auch mit der erweiterten Tabelle
+finden:
+\begin{center}
+\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|}
+\hline
+k& a_k&b_k& q_k&r_k& c_k& d_k\\
+\hline
+ & & & & & 1& 0\\
+0&X^2+X+1&X+1& X & 1& 0& 1\\
+1& X+1& 1& X+1& 0&{\color{red} 1}&{\color{red} 2X}\\
+2& 1& 0& & 0&2X+2& 2X^2+2X\\
+\hline
+\end{tabular}
+\end{center}
+In allen Fällen ist also $(1+X)^{-1} = 2X$.
+\item
+Wegen $m(\alpha)=0$ ist $\alpha^2=-\alpha-1=2\alpha+2$ und damit
+\begin{align*}
+\alpha^3
+&=
+\alpha\cdot \alpha^2 = \alpha (2\alpha +2) =
+2\alpha^2 + 2\alpha
+=
+2(\underbrace{\alpha^2 + \alpha + 1}_{\displaystyle=0} + 2)
+=
+2\cdot 2
+=
+1.
+\qedhere
+\end{align*}
+\end{teilaufgaben}
+\end{loesung}
diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex
index 9ad0800..02429dc 100644
--- a/buch/chapters/30-endlichekoerper/wurzeln.tex
+++ b/buch/chapters/30-endlichekoerper/wurzeln.tex
@@ -3,7 +3,901 @@
%
% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswil
%
+% !TeX spellcheck = de_CH
\section{Wurzeln
\label{buch:section:wurzeln}}
\rhead{Wurzeln}
+Im Körper $\mathbb{Q}$ kann man zum Beispiel die Wurzel aus $2$ nicht
+ziehen.
+Das Problem haben wir in Abschnitt~\ref{buch:section:reelle-zahlen}
+dadurch gelöst, dass wir $\mathbb{Q}$ zu den reellen Zahlen $\mathbb{R}$
+erweitert haben.
+Es ist aber auch möglich, nur die Zahl $\sqrt{2}$ hinzuzufügen,
+so entsteht der Körper $\mathbb{Q}(\sqrt{2})$.
+Das Problem dabei ist, was denn eigentlich $\sqrt{2}$ überhaupt ist.
+Solange man die reellen Zahlen nicht hat, hat man auch $\sqrt{2}$ nicht.
+Das Problem wird akut bei den endlichen Körpern wie zum Beispiel
+$\mathbb{F}_3$,
+da man diese nicht in $\mathbb{R}$ einbetten kann, also keine
+bekannte Menge von Zahlen existiert, in der wir die Wurzel $\sqrt{2}$
+finden könnte.
+
+Im Altertum fiel dieses Problem zunächst den Pythagoreern auf.
+Wenn $\sqrt{2}$ kein Bruch ist, was ist es dann?
+Im 15.~Jahrhundert stellte sich dieses Problem bei den Versuchen, die
+kubische Gleichung allgemein zu lösen, erneut.
+Hier war es die Wurzel $\sqrt{-1}$, die den reellen Zahlen hinzuzufügen
+war.
+In $\mathbb{R}$ hat $\sqrt{-1}$ sicher keinen Platz, also wo existert
+es denn überhaupt?
+Auch der von Descartes eingeführte, eher unglückliche Begriff
+``imaginäre Zahl'' illustriert dieses Dilemma.
+
+Inzwischen hat man sich daran gewöhnt, dass man einfach ein neues Symbol
+wählt, die algebraischen Regeln postuliert, nach denen damit zu rechnen
+ist, und dann hofft oder besser beweist, dass keine Widersprüche auftreten.
+Auf diese Weise kann man einem Körper $\Bbbk$ eine beliebige
+Nullstelle $\alpha$ eines Polynoms $f\in\Bbbk[X]$ mit Koeffizienten
+in $\Bbbk$ hinzufügen und so den Körper $\Bbbk(\alpha)$ konstruieren.
+Trotzdem bleibt die Frage offen: was {\em ist} denn eigentlich $\alpha$?
+
+In diesem Abschnitt werden Wurzeln wie folgt konstruiert.
+Zunächst wird in Abschnitt~\ref{buch:subsection:koerpererweiterungen}
+gezeigt, dass man immer eine Matrix $M_\alpha$ finden kann, welche
+genau die algebraischen Eigenschaften einer Nullstelle $\alpha$ eines
+Polynoms hat.
+Die Frage ``Was ist $\alpha$?'' erhält also die Antwort ``Eine Matrix''.
+Mit diesem Bild lassen sich alle Körperoperationen realisieren, die
+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.
+Wir beginnen in Abschnitt~\ref{buch:subsection:irreduziblepolynome}
+damit, die Polynome, die für die Konstruktion in Frage kommen, etwas
+genauer zu charakterisieren.
+
+\subsection{Irreduzible Polynome
+\label{buch:subsection:irreduziblepolynome}}
+Die Zahlen, die man dem Körper hinzufügen möchte, müssen Nullstellen
+eines Polynoms sein.
+Wir gehen daher davon aus, dass $f\in \Bbbk[X]$ ein Polynom mit
+Koeffizienten in $\Bbbk$ ist, dessen Nullstelle $\alpha$ hinzugefügt
+werden sollen.
+Das Ziel ist natürlich, dass diese Erweiterung vollständig beschrieben
+werden kann durch das Polynom, ganz ohne Bezug zum Beispiel auf einen
+numerischen Wert der Nullstelle, der ohnehin nur in $\mathbb{C}$ sinnvoll
+wäre.
+
+Nehmen wir jetzt an, dass sich das Polynom $f$ faktorisieren lässt.
+Dann gibt es Polynome $g,h\in\Bbbk[X]$ derart, dass $f=g\cdot h$.
+Die Polynome $g$ und $h$ haben geringeren Grad als $f$.
+Setzt man die Nullstelle $\alpha$ ein, erhält man
+$0=f(\alpha)=g(\alpha)h(\alpha)$, daher muss einer der Faktoren
+verschwinden, also $g(\alpha)=0$ oder $h(\alpha)=0$.
+Ohne Beschränkung der Allgemeinheit kann angenommen werden, dass
+$g(\alpha)=0$.
+Die Operation des Hinzufügens der Nullstelle $\alpha$ von $f$
+muss also genauso gut mit $g$ ausgeführt werden können.
+Indem wir diese Überlegung auf $g$ anwenden können wir schliessen,
+dass es ein Polynom $m\in\Bbbk[X]$ kleinstmöglichen Grades geben muss,
+welches $\alpha$ als Nullstelle hat.
+Zusätzlich kann verlangt werden, dass das Polynom normiert ist.
+
+\begin{definition}
+Ein Polynom $f\in \Bbbk[X]$ heisst {\em irreduzibel}, wenn es sich nicht
+in zwei Faktoren $g,h\in \Bbbk[X]$ mit $f=gh$ zerlegen lässt.
+\index{irreduzibles Polynom}%
+\end{definition}
+
+Für die Konstruktion des Körpers $\Bbbk(\alpha)$ muss daher ein irreduzibles
+Polynom verwendet werden.
+
+\begin{beispiel}
+Das Polynom $f(X)=X^2-2$ ist in $\mathbb{Q}[X]$, es hat die beiden
+Nullstellen $\sqrt{2}$ und $-\sqrt{2}$.
+Beide Nullstellen haben die exakt gleichen algebraischen Eigenschaften,
+sie sind mit algebraischen Mitteln nicht zu unterscheiden.
+Nur die Vergleichsrelation ermöglicht, die negative Wurzel von der
+positiven zu unterscheiden.
+Das Polynom kann in $\mathbb{Q}$ nicht faktorisiert werden, denn die
+einzig denkbare Faktorisierung ist $(X-\sqrt{2})(X+\sqrt{2})$, die
+Faktoren sind aber keine Polynome in $\mathbb{Q}[X]$.
+Also ist $f(X) = X^2 - 2$ ein irreduzibles Polynom über $\mathbb Q$.
+
+Man kann das Polynom aber auch als Polynom in $\mathbb{F}_{23}[X]$
+betrachten.
+Im Körper $\mathbb{F}_{23}$ kann man durch probieren zwei Nullstellen
+finden:
+\begin{align*}
+5^2 &= 25\equiv 2\mod 23
+\\
+\text{und}\quad
+18^2 &=324 \equiv 2 \mod 23.
+\end{align*}
+Und tatsächlich ist in $\mathbb{F}_{23}[X]$
+\[
+(X-5)(X-18) = X^2 -23X+90
+\equiv
+X^2 -2 \mod 23,
+\]
+über $\mathbb{F}_{23}$ ist das Polynom $X^2-2$ also reduzibel.
+\end{beispiel}
+
+\begin{beispiel}
+Die Zahl
+\[
+\alpha = \frac{1+i\sqrt{3}}2
+\]
+ist eine Nullstelle des Polynoms $f(X)=X^3-1\in\mathbb{Z}[X]$.
+$\alpha$ enthält aber nur Quadratwurzeln, man würde also eigentlich
+erwarten, dass $\alpha$ Nullstelle eines quadratischen Polynoms ist.
+Tatsächlich ist $f(X)$ nicht irreduzibel, es ist nämlich
+\[
+X^3-1 = (X-1)(X^2+X+1).
+\]
+Da $\alpha$ nicht Nullstelle des ersten Faktors ist, muss es Nullstelle
+des Polynoms $m(X)=X^2+X+1$ sein.
+Der zweite Faktor ist irreduzibel.
+
+Das Polynom $m(X)$ kann man aber auch als Polynom in $\mathbb{F}_7$
+ansehen.
+Dann kann man aber zwei Nullstellen finden,
+\[
+\begin{aligned}
+X&=2&&\Rightarrow& 2^2+2+1=4+2+1&\equiv 0\mod 7
+\\
+X&=4&&\Rightarrow& 4^2+4+1=16+4+1=21&\equiv 0\mod 7.
+\end{aligned}
+\]
+Dies führt auf die Faktorisierung
+\[
+(X-2)(X-4)
+\equiv
+(X+5)(X+3)
+=
+X^2+8X+15
+\equiv
+X^2+X+1\mod 7.
+\]
+Das Polynom $X^2+X+1$ ist daher über $\mathbb{F}_7$ reduzibel und
+das Polynom $X^3-1\in\mathbb{F}_7$ zerfällt daher in Linearfaktoren
+$X^3-1=(X+6)(X+3)(X+5)$.
+\end{beispiel}
+
+
+\subsection{Körpererweiterungen
+\label{buch:subsection:koerpererweiterungen}}
+Nach den Vorbereitungen von
+Abschnitt~\ref{buch:subsection:irreduziblepolynome}
+können wir jetzt definieren, wie die Körpererweiterung
+konstruiert werden soll.
+
+\subsubsection{Erweiterung mit einem irreduziblen Polynom}
+Sei $m\in\Bbbk[X]$ ein irreduzibles Polynome über $\Bbbk$ mit dem Grad
+$\deg m=n$,
+wir dürfen es als normiert annehmen und schreiben es in der Form
+\[
+m(X)
+=
+m_0+m_1X+m_2X^2 + \dots m_{n-1}X^{n-1}+X^n.
+\]
+Wir möchten den Körper $\Bbbk$ um eine Nullstelle $\alpha$ von $m$
+erweitern.
+Da es in $\Bbbk$ keine Nullstelle von $m$ gibt, konstruieren wir
+$\Bbbk(\alpha)$ auf abstrakte Weise, ganz so wie das mit der imaginären
+Einheit $i$ gemacht wurde.
+Die Zahl $\alpha$ ist damit einfach ein neues Symbol, mit dem man
+wie in der Algebra üblich rechnen kann.
+Die einzige zusätzliche Eigenschaft, die von $\alpha$ verlangt wird,
+ist dass $m(\alpha)=0$.
+Unter diesen Bedingungen können beliebige Ausdrücke der Form
+\begin{equation}
+a_0 + a_1\alpha + a_2\alpha^2 + \dots a_k\alpha^k
+\label{buch:endlichekoerper:eqn:ausdruecke}
+\end{equation}
+gebildet werden.
+Aus der Bedingung $m(\alpha)=0$ folgt aber, dass
+\begin{equation}
+\alpha^n = -m_{n-1}\alpha^{n-1} -\dots - m_2\alpha^2 - m_1\alpha - m_0.
+\label{buch:endlichekoerper:eqn:reduktion}
+\end{equation}
+Alle Potenzen mit Exponenten $\ge n$ in
+\eqref{buch:endlichekoerper:eqn:ausdruecke}
+können daher durch die rechte Seite von
+\eqref{buch:endlichekoerper:eqn:reduktion}
+ersetzt werden.
+Als Menge ist daher
+\[
+\Bbbk(\alpha)
+=
+\{
+a_0+a_1\alpha+a_2\alpha^2+\dots+a_{n-1}\alpha^{n-1}\;|\; a_i\in\Bbbk\}
+\]
+ausreichend.
+Die Addition von solchen Ausdrücken und die Multiplikation mit Skalaren
+aus $\Bbbk$ machen $\Bbbk(\alpha)\cong \Bbbk^n$ zu einem Vektorraum,
+die Operationen können auf den Koeffizienten komponentenweise ausgeführt
+werden.
+
+\subsubsection{Matrixrealisierung der Multiplikation mit $\alpha$}
+Die schwierige Operation ist die Multiplikation mit $\alpha$.
+Dazu stellen wir zusammen, wie die Multiplikation mit $\alpha$ auf den
+Basisvektoren von $\Bbbk(\alpha)$ wirkt:
+\[
+\alpha\colon
+\Bbbk^n\to\Bbbk^n
+:
+\left\{
+\begin{aligned}
+ 1 &\mapsto \alpha \\
+\alpha &\mapsto \alpha^2 \\
+\alpha^2&\mapsto \alpha^3 \\
+ &\phantom{m}\vdots\\
+\alpha^{n-2}&\mapsto \alpha^{n-1}\\
+\alpha^{n-1}&\mapsto \alpha^n = -m_0-m_1\alpha-m_2\alpha^2-\dots-m_{n-1}\alpha^{n-1}
+\end{aligned}
+\right.
+\]
+Diese lineare Abbildung hat die Matrix
+\[
+M_{\alpha}
+=
+\begin{pmatrix}
+0 & & & & &-m_0 \\
+1 & 0 & & & &-m_1 \\
+ & 1 & 0 & & &-m_2 \\
+ & & 1 &\ddots& &\vdots \\
+ & & &\ddots& 0 &-m_{n-2}\\
+ & & & & 1 &-m_{n-1}
+\end{pmatrix}.
+\]
+%TODO: Was ist hier die Aussage?
+Aufgrund der Konstruktion die Lineare Abbildung $m(M_\alpha)$,
+die man erhält, wenn
+man die Matrix $M_\alpha$ in das Polynom $m$ einsetzt, jeden Vektor
+in $\Bbbk(\alpha)$ zu Null machen.
+Als Matrix muss daher $m(M_\alpha)=0$ sein.
+Dies kann man auch mit einem Computeralgebra-System nachprüfen.
+
+\begin{beispiel}
+In einem früheren Beispiel haben wir gesehen, dass
+$\alpha=\frac12(-1+\sqrt{3})$
+eine Nullstelle des irreduziblen Polynomes $m(X)=X^2+X+1$ ist.
+Die zugehörige Matrix $M_\alpha$ ist
+\[
+M_{\alpha}
+=
+\begin{pmatrix}
+0&-1\\
+1&-1
+\end{pmatrix}
+\qquad\Rightarrow\qquad
+M_{\alpha}^2
+=
+\begin{pmatrix}
+-1& 1\\
+-1& 0
+\end{pmatrix},\quad
+M_{\alpha}^3
+=
+\begin{pmatrix}
+ 1& 0\\
+ 0& 1
+\end{pmatrix}.
+\]
+Wir können auch verifizieren, dass
+\[
+m(M_\alpha)
+=
+M_\alpha^2+M_\alpha+I
+=
+\begin{pmatrix}
+-1& 1\\
+-1& 0
+\end{pmatrix}
++
+\begin{pmatrix}
+0&-1\\
+1&-1
+\end{pmatrix}
++
+\begin{pmatrix}
+1&0\\
+0&1
+\end{pmatrix}
+=
+\begin{pmatrix}
+0&0\\
+0&0
+\end{pmatrix}.
+\]
+Die Matrix ist also eine mögliche Realisierung für das ``mysteriöse''
+Element $\alpha$.
+Es hat alle algebraischen Eigenschaften von $\alpha$.
+\end{beispiel}
+
+Die Menge $\Bbbk(\alpha)$ kann durch die Abbildung $\alpha\mapsto M_\alpha$
+mit der Menge aller Matrizen
+\[
+\Bbbk(M_\alpha)
+=
+\left\{
+\left.
+a_0I+a_1M_\alpha+a_2M_\alpha^2+\dots+a_{n-1}M_\alpha^{n-1}\;\right|\; a_i\in\Bbbk
+\right\}
+\]
+in eine Eins-zu-eins-Beziehung gebracht werden.
+Diese Abbildung ist ein Algebrahomomorphismus.
+Die Menge $\Bbbk(M_\alpha)$ ist also das Bild des
+Körpers $\Bbbk(\alpha)$ in der Matrizenalgebra $M_n(\Bbbk)$.
+
+\subsubsection{Inverse}
+Im Moment wissen wir noch nicht, wie wir $\alpha^{-1}$ berechnen sollten.
+Wir können aber auch die Matrizendarstellung verwenden.
+Für Matrizen wissen wir selbstverständlich, wie Matrizen invertiert
+werden können.
+Tatsächlich kann man die Matrix $M_\alpha$ direkt invertieren:
+\[
+M_\alpha^{-1}
+=
+\frac{1}{m_0}
+\begin{pmatrix}
+ -m_1 &m_0& & & & \\
+ -m_2 & 0 &m_0& & & \\
+ -m_3 & & 0 & m_0& & \\
+ \vdots & & &\ddots&\ddots& \\
+-m_{n-1}& 0 & 0 & & 0 &m_0\\
+ -1 & 0 & 0 & & 0 & 0
+\end{pmatrix},
+\]
+wie man durch Ausmultiplizieren überprüfen kann:
+\[
+\frac{1}{m_0}
+\begin{pmatrix}
+ -m_1 &m_0& & & & \\
+ -m_2 & 0 &m_0& & & \\
+ -m_3 & & 0 & m_0& & \\
+ \vdots & & &\ddots&\ddots& \\
+-m_{n-1}& 0 & 0 & & 0 &m_0\\
+ -1 & 0 & 0 & & 0 & 0
+\end{pmatrix}
+\begin{pmatrix}
+ 0 & & & & &-m_0 \\
+ 1 & 0 & & & &-m_1 \\
+ & 1 & 0 & & &-m_2 \\
+ & & 1 &\ddots& &\vdots \\
+ & & &\ddots& 0 &-m_{n-2}\\
+ & & & & 1 &-m_{n-1}
+\end{pmatrix}
+=
+\begin{pmatrix}
+1&0&0&\dots&0&0\\
+0&1&0&\dots&0&0\\
+0&0&1&\dots&0&0\\
+\vdots&\vdots&\vdots&\ddots&\vdots\\
+0&0&0&\dots&1&0\\
+0&0&0&\dots&0&1
+\end{pmatrix}
+\]
+Die Invertierung in $\Bbbk(M_\alpha)$ ist damit zwar geklärt, aber
+es wäre viel einfacher, wenn man die Inverse auch in $\Bbbk(\alpha)$
+bestimmen könnte.
+
+Die Potenzen von $M_\alpha^k$ haben in der ersten Spalte genau in
+Zeile $k+1$ eine $1$, alle anderen Einträge in der ersten Spalte
+sind $0$.
+Die erste Spalte eines Elementes
+$a(\alpha)=a_0+a_1\alpha+a_2\alpha^2 +a_{n-1}\alpha^{n-1}$
+besteht daher genau aus den Elementen $a_i$.
+Die Inverse des Elements $a$ kann daher wie folgt gefunden werden.
+Zunächst wird die Matrix $a(M_\alpha)$ gebildet und invertiert.
+Wir schreiben $B=a(M_\alpha)^{-1}$.
+Aus den Einträgen der ersten Spalte kann man jetzt die Koeffizienten
+\[
+b_0=(B)_{11},
+b_1=(B)_{21},
+b_2=(B)_{31},\dots,
+b_{n-1}=(B)_{n,1}
+\]
+ablesen und daraus das Element
+\[
+b(\alpha) = b_0+b_1\alpha+b_2\alpha^2 + \dots + b_{n-1}\alpha^{n-1}
+\]
+bilden.
+Da $b(M_\alpha)=B$ die inverse Matrix von $a(M_\alpha)$ ist, muss $b(\alpha)$
+das Inverse von $a(\alpha)$ sein.
+
+\begin{beispiel}
+Wir betrachten das Polynom
+\[
+m(X) = X^3 + 2X^2 + 2X + 3 \in \mathbb{F}_{7}[X],
+\]
+es ist irreduzibel.
+Sei $\alpha$ eine Nullstelle von $m$, wir suchen das inverse Element zu
+\[
+a(\alpha)=1+2\alpha+2\alpha^2\in\mathbb{F}_{7}(\alpha).
+\]
+Die Matrix $a(M_\alpha)$ bekommt die Form
+\[
+A=\begin{pmatrix}
+ 1& 1& 6\\
+ 2& 4& 5\\
+ 2& 5& 1
+\end{pmatrix}.
+\]
+Die Inverse kann man bestimmen, indem man den
+Gauss-Algorithmus in $\mathbb{F}_{7}$ durchführt.
+Die Arithmetik in $\mathbb{F}_{7}$ ist etwas ungewohnt, insbesondere
+die Pivot-Division ist etwas mühsam, daher sind in
+Abbildung~\ref{buch:endlichekoerper:fig:additionmultiplikation}
+die Additions- und Multiplikationstabellen zusammengestellt.
+\begin{figure}
+\begin{center}
+\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
++&0&1&2&3&4&5&6\\
+\hline
+0&0&1&2&3&4&5&6\\
+1&1&2&3&4&5&6&0\\
+2&2&3&4&5&6&0&1\\
+3&3&4&5&6&0&1&2\\
+4&4&5&6&0&1&2&3\\
+5&5&6&0&1&2&3&4\\
+6&6&0&1&2&3&4&5\\
+\hline
+\end{tabular}
+\qquad
+\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+\cdot
+ &0&1&2&3&4&5&6\\
+\hline
+0&0&0&0&0&0&0&0\\
+1&0&1&2&3&4&5&6\\
+2&0&2&4&6&1&3&5\\
+3&0&3&6&2&5&1&4\\
+4&0&4&1&5&2&6&3\\
+5&0&5&3&1&6&4&2\\
+6&0&6&5&4&3&2&1\\
+\hline
+\end{tabular}
+\end{center}
+\caption{Additions- und Multiplikationstabelle für das Rechnen im
+Galois-Körper $\mathbb{F}_7$.
+Die multiplikative Inverse eines Elements in $a\in\mathbb{F}_7^*$
+findet man, indem man in der Multiplikationstabelle in der Zeile
+$a$ die Spalte mit der $1$ sucht, diese Spalte ist mit der multiplikativen
+Inversen von $a$ angeschrieben.
+\label{buch:endlichekoerper:fig:additionmultiplikation}}
+\end{figure}
+Mit dieser Rechenhilfe kann jetzt der Gaussalgorithmus leicht durchgeführt
+werden:
+\begin{align*}
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1& 1& 6& 1& 0& 0\\
+ 2& 4& 5& 0& 1& 0\\
+ 2& 5& 1& 0& 0& 1\\
+\hline
+\end{tabular}
+&\rightarrow
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1& 1& 6& 1& 0& 0\\
+ 0& 2& 0& 5& 1& 0\\
+ 0& 3& 3& 5& 0& 1\\
+\hline
+\end{tabular}
+\rightarrow
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1& 1& 6& 1& 0& 0\\
+ 0& 1& 0& 6& 4& 0\\
+ 0& 0& 3& 1& 2& 1\\
+\hline
+\end{tabular}
+\\
+&\rightarrow
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1& 1& 6& 1& 0& 0\\
+ 0& 1& 0& 6& 4& 0\\
+ 0& 0& 1& 5& 3& 5\\
+\hline
+\end{tabular}
+\\
+&\rightarrow
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1& 1& 0& 6& 3& 5\\
+ 0& 1& 0& 6& 4& 0\\
+ 0& 0& 1& 5& 3& 5\\
+\hline
+\end{tabular}
+\rightarrow
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+ 1& 0& 0& 0& 6& 5\\
+ 0& 1& 0& 6& 4& 0\\
+ 0& 0& 1& 5& 3& 5\\
+\hline
+\end{tabular}
+\end{align*}
+Für die Durchführung braucht man die Inversen in $\mathbb{F}_7$
+der Pivot-Elemente, sie sind $2^{-1}=4$ und $3^{-1}=5$.
+Im rechten Teil des Tableau steht jetzt die inverse Matrix
+\[
+A^{-1}
+=
+B=\begin{pmatrix}
+ 0& 6& 5\\
+ 6& 4& 0\\
+ 5& 3& 5
+\end{pmatrix}.
+\]
+Daraus können wir jetzt das inverse Element
+\[
+b(\alpha) = 6\alpha+5\alpha^2
+\]
+ablesen.
+Das Produkt $b(X)\cdot a(X)$ ist
+\begin{align*}
+(1+2X+2X^2)(6X+5X^2)
+&=
+10X^4 + 22X^3 + 17X^2 + 6X
+\\
+&=
+3X^4+X^3+3X^2+6X
+\intertext{
+Diese Polynom muss jetzt mit dem Minimalpolynom $m(X)$ reduziert
+werden, wir subtrahieren dazu $3Xm(X)$ und erhalten}
+&=
+-5X^3-3X^2-3X
+\\
+&=
+2X^3+4X^2+4X
+\intertext{Die vollständige Reduktion wird erreicht, indem wir nochmals
+$2m(X)$ subtrahieren:}
+&=
+-6 \equiv 1\mod 7,
+\end{align*}
+das Element $b(\alpha)=6\alpha+5\alpha^2$ ist also das Inverse Element von
+$a(\alpha)=1+2\alpha+2\alpha^2$ in $\mathbb{F}_7(\alpha)$.
+\label{buch:endlichekoerper:beispiel:inversemitmatrix}
+\end{beispiel}
+
+Die Matrixrealisation von $\Bbbk(\alpha)$ führt also auf eine effiziente
+Berechnungsmöglichkeit für das Inverse eines Elements von $\Bbbk(\alpha)$.
+
+\subsubsection{Algebraische Konstruktion}
+Die Matrixdarstellung von $\alpha$ ermöglicht eine rein algebraische
+und für die Rechnung besser geeignete Konstruktion.
+Für jedes Polynom $f\in\Bbbk[X]$ ist $f(M_\alpha)\in M_n(\Bbbk)$.
+Dies definiert einen Homomorphismus
+\[
+\varphi\colon \Bbbk[X] \to M_n(\Bbbk) : f \mapsto f(M_\alpha).
+\]
+Wir haben früher schon gesehen, dass das Bild dieses Homomorphismus
+genau die Menge $\Bbbk(M_\alpha)$ ist.
+Allerdings ist $\varphi$ nicht injektiv, das Polynom $m$ wird zum
+Beispiel auf $\varphi(m) = m(M_\alpha) = 0$ abgebildet.
+
+Der Kern von $\varphi$ besteht aus allen Polynomen $p\in\Bbbk[X]$,
+für die $p(M_\alpha)=0$ gilt.
+Da aber alle Matrizen $E,M_\alpha,\dots,M_\alpha^{n-1}$ linear
+unabhängig sind, muss ein solches Polynom den gleichen Grad haben
+we $m$, und damit ein Vielfaches von $m$ sein.
+Der Kern besteht daher genau aus den Vielfachen von $m(X)$,
+$\ker\varphi = m(X)\Bbbk[X]$.
+
+Es ist nicht a priori klar, dass der Quotient $R/I$ für ein
+Ideal $I\subset R$ ein Körper ist.
+Hier spielt es eine Rolle, dass das von $m$ erzeugte Ideal
+maximal ist im folgenden Sinne.
+
+\begin{definition}
+Ein Ideal $I\subset R$ heisst {\em maximal}, wenn für jedes andere Ideal
+$J$ mit $I\subset J\subset R$ entweder $I=J$ oder $J=R$ gilt.
+\end{definition}
+
+\begin{beispiel}
+Die Ideale $p\mathbb{Z}\subset \mathbb{Z}$ sind maximal genau dann, wenn
+$p$ eine Primzahl ist.
+
+TODO: XXX Begründung
+\end{beispiel}
+
+\begin{satz}
+Der Ring $R/I$ ist genau dann ein Körper, wenn $I$ ein maximales Ideal ist.
+\end{satz}
+
+\begin{proof}[Beweis]
+\end{proof}
+
+Ein irreduzibles Polynom $m\in\Bbbk[X]$ erzeugt ein maximales Ideal,
+somit ist $\Bbbk[X]/m\Bbbk[X]\cong \Bbbk(M_\alpha) \cong \Bbbk(\alpha)$.
+
+\subsubsection{Reduktion modulo $m$}
+Die algebraische Konstruktion hat gezeigt, dass die arithmetischen
+Operationen im Körper $\Bbbk(\alpha)$ genau die Operationen
+in $\Bbbk[X]/m\Bbbk[X]$ sind.
+Eine Zahl in $\Bbbk(\alpha)$ wird also durch ein Polynom vom
+$n-1$ dargestellt.
+Addieren und Subtrahieren erfolgen Koeffizientenweise in $\Bbbk$.
+Bei der Multiplikation entsteht möglicherwise ein Polynom grösseren
+Grades, mit dem Polynomdivisionsalgorithmus kann der Rest bei Division
+durch $m$ ermittelt werden.
+
+\begin{beispiel}
+Das Polyonom $f=X^5+X^4+X^3+X^2+X^1+1\in\mathbb{F}_7[X]$ soll modulo
+$m(X)=X^3+2X^2+2X^2+3$ reduziert werden.
+Wir führen die Polynomdivision in $\mathbb{F}_7[X]$ durch, die
+Multiplikationstabelle von $\mathbb{F}_7$ in
+Abbildung~\ref{buch:endlichekoerper:fig:additionmultiplikation}
+ist dabei wieder hilfreich.
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcrcrcrcrcrcrcrcr}
+X^5&+& X^4&+& X^3&+& X^2&+& X&+&1&:&X^3&+&2X^2&+&2X&+&3&=&X^2&+&6X&+&1\rlap{$\mathstrut=q$}\\
+\llap{$-($}X^5&+&2X^4&+&2X^3&+&3X^2\rlap{$)$}& & & & & & & & & & & & & & & & & & \\
+\cline{1-7}
+ & &6X^4&+&6X^3&+&5X^2&+& X& & & & & & & & & & & & & & & & \\
+ & &\llap{$-($}6X^4&+&5X^3&+&5X^2&+&4X\rlap{$)$}& & & & & & & & & & & & & & & & \\
+\cline{3-9}
+ & & & & X^3& & &+&4X&+&1& & & & & & & & & & & & & & \\
+ & & & &\llap{$-($}X^3&+&2X^2&+&2X&+&3\rlap{$)$}& & & & & & & & & & & & & & \\
+\cline{5-11}
+ & & & & & &5X^2&+&2X&+&5\rlap{$\mathstrut=r$}& & & & & & & & & & & & & & \\
+\end{array}
+\]
+Die Kontrolle
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcrcr}
+\llap{$($}X^2&+& 6X&+& 1\rlap{$)$}&\cdot&\llap{$($} X^3&+&2X^2&+&2X&+&3\rlap{$)$}\\
+\cline{1-13}
+ & & & & & & X^3&+&2X^2&+&2X&+&3\\
+ & & & &6X^4& + &5X^3&+&5X^2&+&4X& & \\
+ & & X^5&+&2X^4& + &2X^3&+&3X^2& & & & \\
+\cline{3-13}
+ & & X^5&+& X^4& + & X^3&+&3X^2&+&6X&+&3\rlap{$\phantom{)}=q\cdot m$}\\
+ & & & & & & & &\llap{$+($}5X^2&+&2X&+&5\rlap{$)=r$}\\
+\cline{3-13}
+ & & X^5&+& X^4& + & X^3&+& X^2&+& X&+&1\\
+\cline{3-13}
+\end{array}
+\]
+zeigt $f=qm+r$ und damit die Korrektheit der Rechnung.
+\end{beispiel}
+
+Die Identität $m(\alpha)=0$ kann aber auch wie folgt interpretiert werden.
+Sei der Grad von $f$ mindestens so gross wie der von $m$, also
+$l=\deg f\ge \deg m=n$.
+Indem man mit $\alpha^{l-n}$ multipliziert, erhält man die Relation
+\[
+\alpha^l + m_{n-1}\alpha^{l-1} + m_{n-2}\alpha^{l-2}+\dots +a_1\alpha^{l-n+1} + a_0\alpha^{l-n} = 0.
+\]
+
+Ist $f_l$ der führende Koeffizient des Polynoms $f$, dann ist
+$f-f_0mX^{n-l}$ ein Polynom vom Grad $l-1$, welches modulo $m$
+mit $f$ übereinstimmt.
+Indem man dies wiederholt, kann man also die Reduktion finden, ohne
+den Polynomdivisionsalgorithmus durchzuführen.
+Man erhält auf diese Weise zwar den Quotienten $q$ nicht, aber den
+Rest $r$ kann man trotzdem bekommen.
+
+\begin{beispiel}
+Wir wenden den eben beschriebenen Algorithmus wieder auf das
+Polynom $f=X^5+X^4+X^3+X^2+X+1$ an und erhalten:
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcr}
+X^5&+& X^4&+& X^3&+& X^2&+& X&+&1\\
+\llap{$-($}X^5&+&2X^4&+&2X^3&+&3X^2\rlap{$\mathstrut =X^2m)$}& & & & \\
+\cline{1-11}
+ & &6X^4&+&6X^3&+&5X^2&+& X&+&1\\
+ & &\llap{$-($}6X^4&+&5X^3&+&5X^2&+&4X\rlap{$\mathstrut =6Xm)$}& & \\
+\cline{3-11}
+ & & & & X^3& & &+&4X&+&1\\
+ & & & & \llap{$-($}X^3&+&2X^2&+&2X&+&3\rlap{$\mathstrut =m)$}\\
+\cline{5-11}
+ & & & & & &5X^2&+&2X&+&5\rlap{$\mathstrut =r$}\\
+\end{array}
+\]
+Dies ist derselbe Rest wie wir mit dem Divisionsalgorithmus
+gefunden haben.
+\end{beispiel}
+
+Diese Form des Reduktionsalgorithmus ist besonders leicht durchzuführen
+in einem Körper $\mathbb{F}_2$, da dort die Addition und die Subtraktion
+der Koeffizienten übereinstimmen.
+Die Multiplikation mit $X$ ist nichts anders als ein Shift der
+Koeffizienten.
+
+\subsubsection{Multiplikative Inverse}
+Die schwierigste Operation in $\Bbbk(\alpha)$ ist die Division.
+Wie bei der Berechnung der Inversion in einem Galois-Körper $\mathbb{F}_p$
+kann dafür der euklidische Algorithmus verwendet werden.
+Sei also $f\in\Bbbk[X]$ ein Polynom vom Grad $\deg f <\deg m$, es soll
+das multiplikative Inverse gefunden werden.
+Da $m$ ein irreduzibles Polynom ist, müssen $f$ und $m$ teilerfremd sein.
+Der euklidische Algorithmus liefert zwei Polynome $s,t\in\Bbbk[X]$ derart,
+dass
+\[
+sf+tm=1.
+\]
+Reduzieren wir modulo $m$, wird daraus $af=1$ in $\Bbbk[X]/m\Bbbk[X]$.
+Das Polynom $a$, reduziert module $m$, ist also die multiplikative
+Inverse von $f$.
+
+Bei der praktischen Durchführung des euklidischen Algorithmus ist der
+letzte Rest $r_{n-1}$ oft nicht $1$ sondern ein anderes Element von
+$\mathbb{F}_p^*$.
+Die Linearkombination von $f$ und $m$ mit den berechneten Faktoren
+$s$ und $t$ ist daher auch nicht $1$, sondern
+\[
+sf+tm=r_{n-1}.
+\]
+Da aber alle Elemente in $\mathbb{F}_p^*$ invertierbar sind, kann man
+durch $r_{n-1}$ dividieren, was
+\[
+r_{n-1}^{-1}sf+r_{n-1}^{-1}tm=1
+\]
+ergibt.
+Also ist $r_{n-1}^{-1}s$ die gesuchte Inverse in $\mathbb{F}_p(\alpha)$,
+dies passiert auch im folgenden Beispiel.
+
+\begin{beispiel}
+Auf
+Seite~\pageref{buch:endlichekoerper:beispiel:inversemitmatrix}
+haben wir die multiplikative Inverse von
+$f=2X^2+2X+1\in\mathbb{F}_7[X]/m\mathbb{F}_7[X]$
+mit $m = X^3 + 2X^2 + 2X + 3$
+mit Hilfe von Matrizen berechnet, hier soll sie jetzt nochmals
+mit dem euklidischen Algorithmus berechnet werden.
+
+Zunächst müssen wir den euklidischen Algorithmus für die beiden Polynome
+$f$ und $m$ durchführen.
+Der Quotient $m:f$ ist:
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcrcrcrcr}
+ X^3&+&2X^2&+&2X&+&3&:&2X^2&+&2X&+&1&=&4X&+&4\rlap{$\mathstrut=q_0$}\\
+\llap{$-($}X^3&+& X^2&+&4X\rlap{$)$}& & & & & & & & & & & & \\ \cline{1-5}
+ & & X^2&+&5X&+&3& & & & & & & & & & \\
+ &&\llap{$-(\phantom{2}$}X^2&+& X&+&4\rlap{$)$}& & & & & & & & & & \\ \cline{3-7}
+ & & & &4X&+&6\rlap{$\mathstrut=r_0$}& & & & & & & & & &
+\end{array}
+\]
+Jetzt muss der Quotient $f:r_0$ berechnet werden:
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcrcrcrcr}
+ 2X^2&+&2X&+&1&:&4X&+&6&=&4X&+&5\rlap{$\mathstrut=q_1$}\\
+\llap{$-($}2X^2&+&3X\rlap{$)$}& & & & & & & & \\ \cline{1-3}
+ & &6X&+&1& & & & & & \\
+ & &\llap{$-($}6X&+&2\rlap{$)$}& & & & & & \\ \cline{3-5}
+ & & & &6\rlap{$\mathstrut=r_1$}& & & & & & & &
+\end{array}
+\]
+Da der Rest $r_1\in\mathbb{F}_7^*$ liegt, gibt die nächste Division
+natürlich den Rest $0$ und der letzte nicht verschwindende Rest ist
+$r_{1}=6$:
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcr}
+4X&+&6&:&6&=&3X&+&1\rlap{$\mathstrut=q_2$} \\
+\llap{$-($}4X\rlap{$)$}& & & & & & & & \\ \cline{1-1}
+ 0&+&6& & & & & & \\
+ & &\llap{$-($}6\rlap{$)$}& & & & & &\\ \cline{3-3}
+ & &0\rlap{$\mathstrut=r_2$}& & & & & &
+\end{array}
+\]
+Damit ist der euklidische Algorithmus abgeschlossen.
+
+Durch Ausmultiplizieren der Matrizen $Q(-q_i)$ können wir jetzt auch die
+Faktoren $s$ und $t$ finden.
+\begin{align*}
+Q=\begin{pmatrix}
+s&t\\
+*&*
+\end{pmatrix}
+&= Q(q_2)Q(q_1)Q(q_0)
+=
+\begin{pmatrix}0&1\\1&-q_2\end{pmatrix}
+\begin{pmatrix}0&1\\1&-q_1\end{pmatrix}
+\begin{pmatrix}0&1\\1&-q_0\end{pmatrix}
+\\
+&=
+\begin{pmatrix}
+0&1\\
+1&4X+6
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\
+1&3X+2
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\
+1&3X+3
+\end{pmatrix}
+\\
+&=
+\begin{pmatrix}
+0&1\\
+1&4X+6
+\end{pmatrix}
+\begin{pmatrix}
+ 1&3X+3\\
+3X+2&2X^2 + X
+\end{pmatrix}
+\\
+&=
+\begin{pmatrix}
+3X+2 &2X^2+X\\
+1+(4X+6)(3X+2) &3X+3 + (4X+6)(2X^2+X)
+\end{pmatrix}
+\\
+&=
+\begin{pmatrix}
+ 3X+2 & 2X^2 +X\\
+5X^2+5X+6 & X^3+2X^2+2X+6
+\end{pmatrix}
+\end{align*}
+Daraus liest man
+\[
+s
+=
+2X^2+X
+\qquad\text{und}\qquad
+t
+=
+3X+2
+\]
+ab.
+Wir überprüfen, ob die Koeffizienten der ersten Zeile tatsächlich $m$ und $f$
+zu $r_1=6$ kombinieren.
+Es ist
+\begin{align*}
+(3X+2)\cdot m + (2X^2+X)\cdot f
+&=
+(3X+2)
+(X^3+3X^2+X+2)
++
+(2X^2+X)
+(2X^2+2X+1)
+=
+6=r_1
+\end{align*}
+Die multiplikative Inverse ist daher
+$
+r_1^{-1}(2X^2 + X)
+=
+6^{-1}
+(2X^2 + X)
+=
+6
+(2X^2 + X)
+=
+5X^2+6X$,
+was mit dem Beispiel von
+Seite~\pageref{buch:endlichekoerper:beispiel:inversemitmatrix}
+übereinstimmt.
+\end{beispiel}
+
+Besonders einfach ist die Rechung für $\Bbbk=\mathbb{F}_2$.
+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
+
+
+