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