diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/chapters/30-endlichekoerper/chapter.tex | 3 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/euklid.tex | 80 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/galois.tex | 146 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/images/Makefile | 6 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/images/fermat.pdf | bin | 0 -> 24470 bytes | |||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/images/fermat.tex | 138 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/wurzeln.tex | 44 |
7 files changed, 345 insertions, 72 deletions
diff --git a/buch/chapters/30-endlichekoerper/chapter.tex b/buch/chapters/30-endlichekoerper/chapter.tex index 1a0a323..b4c602e 100644 --- a/buch/chapters/30-endlichekoerper/chapter.tex +++ b/buch/chapters/30-endlichekoerper/chapter.tex @@ -8,13 +8,14 @@ \lhead{Endliche Körper} \rhead{} Aus den ganzen Zahlen $\mathbb{Z}$ entsteht ein Körper, indem wir Brüche -bilden alle von $0$ verschiedenen Nenner zulassen. +bilden und dabei alle von $0$ verschiedenen Nenner zulassen. Der Körper der rationalen Zahlen $\mathbb{Q}$ enthält unendliche viele Zahlen und hat zusätzlich die sogenannte archimedische Eigenschaft, nämliche dass es zu zwei positiven rationalen Zahlen $a$ und $b$ immer eine ganze Zahl $n$ gibt derart, dass $na>b$. Dies bedeutet auch, dass es in den rationalen Zahlen beliebig grosse Zahlen gibt. + Man kann aus den ganzen Zahlen aber auch eine Reihe von Körpern ableiten, die diese Eigenschaft nicht haben. Nicht überraschend werden die ersten derartigen Körper, die wir diff --git a/buch/chapters/30-endlichekoerper/euklid.tex b/buch/chapters/30-endlichekoerper/euklid.tex index 0bf3016..a75046f 100644 --- a/buch/chapters/30-endlichekoerper/euklid.tex +++ b/buch/chapters/30-endlichekoerper/euklid.tex @@ -8,18 +8,33 @@ \rhead{Der euklidische Algorithmus} Der euklidische Algorithmus bestimmt zu zwei gegebenen ganzen Zahlen $a$ und $b$ den grössten gemeinsamen Teiler $g$. -Zusätzlich findet er ganze Zahlen $s$ und $t$ derart, dass + +\begin{definition} +\label{buch:endliche-koerper:def:ggt} +Der grösste gemeinsame Teiler von $a$ und $b$ ist die grösste +ganze Zahl $g$, die sowohl $a$ als auch $b$ teilt: $g|a$ und +$g|b$. +\index{grösster gemeinsamer Teiler}% +\index{ggT}% +\end{definition} + +Zusätzlich findet der euklidische Algorithmus ganze Zahlen $s$ +\index{euklidischer Algorithmus}% +und $t$ derart, dass \[ sa + tb = g. \] In diesem Abschnitt soll der Algorithmus zunächst für ganze Zahlen vorgestellt werden, bevor er auf Polynome verallgemeinert und dann in Matrixform niedergeschrieben wird. +Die Matrixform ermöglicht, einfach zu implementierende iterative +Algorithmen für die Zahlen $s$ und $t$ un später auch für die +Berechnung des kleinsten gemeinsamen Vielfachen zu finden. % % Der euklidische Algorithmus für ganze Zahlen % -\subsection{Ganze Zahlen} +\subsection{Grösster gemeinsamer Teiler ganzer Zahlen} Gegeben sind zwei ganze Zahlen $a$ und $b$ und wir dürfen annehmen, dass $a\ge b$. Gesucht ist der grösste gemeinsame Teiler $g$ von $a$ und $b$. @@ -55,11 +70,11 @@ neuen Quotienten $q_1$ und einen neuen Rest $r_1$ liefert mit $a_1-q_1b_1=r_1$. So entstehen vier Folgen von Zahlen $a_k$, $b_k$, $q_k$ und $r_k$ derart, dass in jedem Schritt gilt \begin{align*} -a_k - q_kb_k &= r_k & g&|a_k & g&|b_k & a_k &= b_{k-1} & b_k = r_{k-1} +a_k - q_kb_k &= r_k & g&|a_k & g&|b_k & a_k &= b_{k-1} & b_k = r_{k-1}. \end{align*} Der Algorithmus bricht im Schritt $n$ ab, wenn $r_{n+1}=0$. Der letzte nicht verschwindende Rest $r_n$ muss daher der grösste gemeinsame -Teiler sein: $g=r_n$. +Teiler $g$ von $a$ und $b$ sein: $g=r_n$. \begin{beispiel} \label{buch:endlichekoerper:beispiel1} @@ -131,7 +146,7 @@ In jedem Schritt arbeitet man mit zwei ganzen Zahlen $a_k$ und $b_k$, die wir als zweidimensionalen Spaltenvektor betrachten können. Der Algorithmus macht aus $a_k$ und $b_k$ die neuen Zahlen $a_{k+1} = b_k$ und $b_{k+1} = r_k = a_k - q_kb_k$, dies -kann man als +kann man als die Matrixoperation \[ \begin{pmatrix} a_{k+1} \\ b_{k+1} \end{pmatrix} = @@ -143,7 +158,7 @@ kann man als schreiben. Der Algorithmus bricht ab, wenn die zweite Komponente des Vektors $=0$ ist, in der ersten steht dann der grösste gemeinsame Teiler. -Hier ist die Durchführung des Algorithmus in Matrix-Schreibweise: +Hier die Durchführung des Algorithmus in Matrix-Schreibweise: \begin{align*} \begin{pmatrix} 23205 \\ 6800 \end{pmatrix} &= @@ -196,16 +211,16 @@ beschreiben. \begin{algorithmus}[Euklid] \label{lifting:euklid} -Der Algorithmus operiert auf zweidimensionalen Zustandsvektoren +Der Algorithmus operiert auf zweidimensionalen Vektoren $x\in\mathbb Z^2$ wie folgt: \begin{enumerate} -\item Initialisiere den Zustandsvektor mit den ganzen Zahlen $a$ und $b$: -$\displaystyle x = \begin{pmatrix}a\\b\end{pmatrix}$ +\item Initialisiere den Vektor mit den ganzen Zahlen $a$ und $b$: +$\displaystyle x = \begin{pmatrix}x_1\\x_2\end{pmatrix}=\begin{pmatrix}a\\b\end{pmatrix}$ \item Bestimme den Quotienten $q$ als die grösste ganze Zahl, für die $qx_2\le x_1$ gilt. -\item Berechne den neuen Zustandsvektor als $Q(q)x$. -\item Wiederhole Schritte 2 und 3 bis die zweite Komponente des Zustandsvektors +\item Berechne den neuen Vektor als $Q(q)x$. +\item Wiederhole Schritte 2 und 3 bis die zweite Komponente des Vektors verschwindet. Die erste Komponente ist dann der gesuchte grösste gemeinsame Teiler. \end{enumerate} @@ -319,13 +334,11 @@ Q(q) = \begin{pmatrix} 0 & 1 \\ 1 & -q \end{pmatrix} \] lässt sich mit genau einer Multiplikation und einer Addition berechnen. -Dies ist die Art von Matrix, die wir für die Implementation der -Wavelet-Transformation anstreben. % % Vereinfachte Durchführung des euklidischen Algorithmus % -\subsection{Vereinfachte Durchführung +\subsection{Iterative Durchführung des erweiterten euklidischen Algorithmus \label{buch:endlichekoerper:subsection:matrixschreibweise}} Die Durchführung des euklidischen Algorithmus mit Hilfe der Matrizen $Q(q_k)$ ist etwas unhandlich. @@ -334,7 +347,7 @@ dargestellt werden, die leichter als Programm zu implementieren ist. In Abschnitt~\ref{buch:endlichekoerper:subsection:matrixschreibweise} wurde gezeigt, dass das Produkt der aus den Quotienten $q_k$ gebildeten -Matrizen $Q(q_k)$ berechnet werden müssen. +Matrizen $Q(q_k)$ berechnet werden muss. Dazu beachten wir zunächst, dass die Multiplikation mit der Matrix $Q(q_k)$ die zweite Zeile in die erste Zeile verschiebt: \[ @@ -357,7 +370,7 @@ u-q_kc&v-q_kd \] Die Matrizen \[ -Q_k = Q(q_k)Q(q_{k-1})\dots Q(q_0) +Q_k = Q(q_k)Q(q_{k-1})\cdots Q(q_0) \] haben daher jeweils für aufeinanderfolgende Werte vo $k$ eine Zeile gemeinsam. @@ -419,7 +432,7 @@ gesetzt werden muss. Mit diesen Notationen kann man den Algorithmus jetzt in der früher verwendeten Tabelle durchführen, die man um die zwei -Spalten $c_k$ und $d_k$ hinzufügt und die Werte in dieser +Spalten $c_k$ und $d_k$ erweitert und die Werte in dieser Spalte mit Hilfe der Rekursionsformeln~\eqref{buch:endlichekoerper:eqn:cdrekursion} aus den initialen Werten~\eqref{buch:endlichekoerper:eqn:cdinitial} @@ -428,7 +441,7 @@ berechnet. \begin{beispiel} Wir erweitern das Beispiel von Seite~\pageref{buch:endlichekoerper:beispiel1} zur Bestimmung des grössten gemeinsamen Teilers von $76415$ und $23205$ -zur Berechnung der Koeffizienten $c_k$ und $d_k$ +um die Spalten zur Berechnung der Koeffizienten $c_k$ und $d_k$ Wir schreiben die gefundenen Zahlen in eine Tabelle: \begin{center} \label{buch:endlichekoerper:beispiel1erweitert} @@ -503,7 +516,7 @@ Tabelle vertauscht wurden. % % Der euklidische Algorithmus für Polynome % -\subsection{Polynome} +\subsection{Grösster gemeinsare Teiler von Polynomen} Der Ring $\mathbb{Q}[X]$ der Polynome in der Variablen $X$ mit rationalen Koeffizienten\footnote{Es kann auch ein beliebiger anderer Körper für die Koeffizienten verwendet werden. @@ -579,7 +592,7 @@ ta+sb (X^4+X^3-7X^2-X+6) \\ &= --4X^2+4X+8 +-4X^2+4X+8, \end{align*} und dies ist tatsächlich der gefundene grösste gemeinsame Teiler. Die zweite Zeile von $Q$ gibt uns die Polynomfaktoren, mit denen @@ -621,6 +634,8 @@ $ua-vb = ab/g - ab/g = 0$, wie erwartet. % \subsection{Das kleinste gemeinsame Vielfache \label{buch:subsection:daskgv}} +\index{kleinstes gemeinsames Vielfaches}% +\index{kgV}% Das kleinste gemeinsame Vielfache zweier Zahlen $a$ und $b$ ist \[ \operatorname{kgV}(a,b) @@ -631,8 +646,8 @@ Wir suchen nach einen Algorithmus, mit dem man das kleinste gemeinsame Vielfache effizient berechnen kann. Die Zahlen $a$ und $b$ sind beide Vielfache des grössten gemeinsamen -Teilers $g=\operatorname{ggT}(a,b)$, es gibt also Zahlen $u$ und $v$ derart, -dass $a=ug$ und $b=vg$. +Teilers $g=\operatorname{ggT}(a,b)$. +Es gibt daher Zahlen $u$ und $v$ derart, dass $a=ug$ und $b=vg$. Wenn $t$ ein gemeinsamer Teiler von $u$ und $v$ ist, dann ist $tg$ ein grösserer gemeinsamer Teiler von $a$ und $b$. Dies kann nicht sein, also müssen $u$ und $v$ teilerfremd sein. @@ -641,6 +656,7 @@ Die Bestimmung des kleinsten gemeinsamen Vielfachen ist also gleichbedeutend mit der Bestimmung der Zahlen $u$ und $v$. Die definierende Eigenschaften von $u$ und $v$ kann man in Matrixform als +\index{Matrixform des kgV-Algorithmus}% \begin{equation} \begin{pmatrix} a\\b @@ -669,7 +685,7 @@ Algorithmus beschreiben, ergeben ihn als \operatorname{ggT}(a,b)\\0 \end{pmatrix} = -Q(q_n)Q(q_{n-1}) \dots Q(q_1)Q(q_0) +Q(q_n)Q(q_{n-1}) \cdots Q(q_1)Q(q_0) \begin{pmatrix}a\\b\end{pmatrix}. \] Indem wir die Matrizen $Q(q_n)$ bis $Q(q_0)$ auf die linke Seite der @@ -679,7 +695,7 @@ Gleichung schaffen, erhalten wir = Q(q_0)^{-1} Q(q_1)^{-1} -\dots +\cdots Q(q_{n-1})^{-1} Q(q_n)^{-1} \begin{pmatrix}\operatorname{ggT}(a,b)\\0\end{pmatrix}. @@ -692,15 +708,14 @@ K = Q(q_0)^{-1} Q(q_1)^{-1} -\dots +\cdots Q(q_{n-1})^{-1} Q(q_n). \] Insbesondere ist die Matrix $K$ die Inverse der früher gefundenen Matrix $Q$. -Die Berechnung der Matrix $K$ als Inverse von $Q$ ist nicht sehr -effizient. +Die Berechnung der Matrix $K$ als Inverse von $Q$ ist nicht schwierig. Genauso wie es möglich war, das Produkt $Q$ der Matrizen $Q(q_k)$ iterativ zu bestimmen, muss es auch eine Rekursionsformel für das Produkt der inversen Matrizen $Q(q_k)^{-1}$ geben. @@ -709,7 +724,7 @@ Schreiben wir die gesuchte Matrix \[ K_k = -Q(q_0)^{-1}\dots Q(q_{k-1})^{-1} +Q(q_0)^{-1}\cdots Q(q_{k-1})^{-1} = \begin{pmatrix} e_k & e_{k-1}\\ @@ -825,13 +840,12 @@ va \] \end{beispiel} +\subsection{Kleinstes gemeinsames Vielfaches von Polynomen} Der erweiterte Algorithmus kann auch dazu verwendet werden, das kleinste gemeinsame Vielfache zweier Polynome zu berechnen. Dies wird zum Beispiel bei der Decodierung des Reed-Solomon-Codes in Kapitel~\ref{chapter:reedsolomon} verwendet. -\subsubsection{Polynome -\label{buch:endlichekoerper:eqn:polynomkgv}} Im Beispiel auf Seite~\pageref{buch:endlichekoerper:eqn:polynomggt} wird der grösste gemeinsame Teiler der Polynome \[ @@ -844,6 +858,8 @@ b = X^4 + X^3 -7X^2 -X + 6 berechnet. Dies kann jetzt erweitert werden für die Berechnung des kleinsten gemeinsamen Vielfachen. +\index{kleinstes gemeinsames Vielfaches von Polynomen}% +\index{kgV von Polynomen}% \begin{beispiel} Die Berechnungstabelle nur für die Spalten $e_k$ und $f_k$ ergibt @@ -890,8 +906,9 @@ Daraus ergibt sich das kleinste gemeinsame Vielfache auf zwei verschiedene Weise Die beiden Berechnungsmöglichkeiten stimmen wie erwartet überein. \end{beispiel} -\subsubsection{Anwendung: Decodierung des Reed-Solomon-Codes} +\subsection{Anwendung: Decodierung des Reed-Solomon-Codes} Der Reed-Solomon-Code verwendet Polynome zur Codierung der Daten, +\index{Reed-Solomon-Code}% dies wird in Kapitel~\ref{chapter:reedsolomon} im Detail beschrieben. Bei der Decodierung muss der Faktor $u$ für zwei gegebene Polynome $n(X)$ und $r(X)$ bestimmt werden. @@ -902,6 +919,7 @@ Algorithmus braucht. Daraus lässt sich genügend Information gewinnen, um die Faktoren $u$ und $v$ zu bestimmen. Das Video \url{https://youtu.be/uOLW43OIZJ0} von Edmund Weitz +\index{Weitz, Edmund} erklärt die Theorie hinter dieser Teilaufgabe anhand von Beispielen. \begin{beispiel} diff --git a/buch/chapters/30-endlichekoerper/galois.tex b/buch/chapters/30-endlichekoerper/galois.tex index c7147bf..7ffef0b 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 sind 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 Binary files differnew file mode 100644 index 0000000..4513e62 --- /dev/null +++ b/buch/chapters/30-endlichekoerper/images/fermat.pdf diff --git a/buch/chapters/30-endlichekoerper/images/fermat.tex b/buch/chapters/30-endlichekoerper/images/fermat.tex new file mode 100644 index 0000000..6cdafaa --- /dev/null +++ b/buch/chapters/30-endlichekoerper/images/fermat.tex @@ -0,0 +1,138 @@ +% +% fermat.tex -- Illustration zum kleinen Satz von Fermat +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math,calc} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\s{34} + +\definecolor{farbe1}{rgb}{0.0,0.4,0.0} +\definecolor{farbe2}{rgb}{0.0,1.0,1.0} +\definecolor{farbe3}{rgb}{0.0,0.4,0.6} +\definecolor{farbe4}{rgb}{0.0,0.0,0.8} +\definecolor{farbe5}{rgb}{0.4,0.0,1.0} +\definecolor{farbe6}{rgb}{0.8,0.0,0.0} +\definecolor{farbe7}{rgb}{0.8,0.4,0.4} +\definecolor{farbe8}{rgb}{1.0,0.8,0.0} + +\def\perle#1#2#3{ + \fill[color=#3] ($#1+({#2*0.15},0)$) circle[radius=0.075]; +} + +\def\perlena#1#2#3#4#5#6{ + \draw #1 -- ($#1+({0.15*9},0)$); + \perle{#1}{0}{#2} + \perle{#1}{1}{#3} + \perle{#1}{2}{#4} + \perle{#1}{3}{#5} + \perle{#1}{4}{#6} +} +\def\perlenb#1#2#3#4#5#6{ + \perle{#1}{5}{#2} + \perle{#1}{6}{#3} + \perle{#1}{7}{#4} + \perle{#1}{8}{#5} + \perle{#1}{9}{#6} +} + +\begin{scope}[xshift=3cm] +\draw (0,0) circle[radius=4]; +\foreach \k in {-1,...,8}{ + \draw (0,0) -- ({90+\k*\s}:4); +} +\foreach \k in {1,...,8}{ + \node at ({90+\s*(\k-0.5)}:3.7) {$A_{\k\mathstrut}$}; +} + +\pgfmathparse{90-(360-9*\s)/2-\s} +\xdef\b{\pgfmathresult} +\foreach \d in {-10,-5,...,10}{ + \fill ({\b+\d}:2.8) circle[radius=0.04]; +} +\node at ({90-(\s/2)}:3.7) {$A_{p\mathstrut}$}; + +\node at (-4,4) {$s_1$}; +\node at (-3.8,2.6) {$s_2$}; +\node at (-4.8,0.6) {$s_3$}; +\node at (-4.2,-2) {$s_4$}; +\node at (-4,-4) {$s_5$}; + +\perlena{({-3*sin(-0.5*\s)-0.54},{3*cos(-0.5*\s)})}{farbe8}{farbe1}{farbe2}{farbe3}{farbe4} +\perlenb{({-3*sin(-0.5*\s)-0.54},{3*cos(-0.5*\s)})}{farbe5}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0} + +\perlena{({-3*sin(0.5*\s)-0.74},{3*cos(0.5*\s)})}{farbe1}{farbe2}{farbe3}{farbe4}{farbe5} +\perlenb{({-3*sin(0.5*\s)-0.74},{3*cos(0.5*\s)})}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8} + +\perlena{({-3*sin(1.5*\s)-0.74},{3*cos(1.5*\s)-0.2})}{farbe2}{farbe3}{farbe4}{farbe5}{farbe6} +\perlenb{({-3*sin(1.5*\s)-0.74},{3*cos(1.5*\s)-0.2})}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1} + +\perlena{({-3*sin(2.5*\s)-0.0},{3*cos(2.5*\s)-0.0})}{farbe3}{farbe4}{farbe5}{farbe6}{farbe7} +\perlenb{({-3*sin(2.5*\s)-0.0},{3*cos(2.5*\s)-0.0})}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1}{farbe2} + +\perlena{({-3*sin(3.5*\s)-0.74},{3*cos(3.5*\s)+0.2})}{farbe4}{farbe5}{farbe6}{farbe7}{black,opacity=0} +\perlenb{({-3*sin(3.5*\s)-0.74},{3*cos(3.5*\s)+0.2})}{black,opacity=0}{farbe8}{farbe1}{farbe2}{farbe3} + +\perlena{({-3*sin(4.5*\s)-0.74},{3*cos(4.5*\s)})}{farbe5}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0} +\perlenb{({-3*sin(4.5*\s)-0.74},{3*cos(4.5*\s)})}{farbe8}{farbe1}{farbe2}{farbe3}{farbe4} + +\perlena{({-3*sin(5.5*\s)-0.64},{3*cos(5.5*\s)})}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8} +\perlenb{({-3*sin(5.5*\s)-0.64},{3*cos(5.5*\s)})}{farbe1}{farbe2}{farbe3}{farbe4}{farbe5} + +\perlena{({-3*sin(6.5*\s)-0.64},{3*cos(6.5*\s)})}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1} +\perlenb{({-3*sin(6.5*\s)-0.64},{3*cos(6.5*\s)})}{farbe2}{farbe3}{farbe4}{farbe5}{farbe6} + +\perlena{({-3*sin(7.5*\s)-1.14},{3*cos(7.5*\s)+0.1})}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1}{farbe2} +\perlenb{({-3*sin(7.5*\s)-1.14},{3*cos(7.5*\s)+0.1})}{farbe3}{farbe4}{farbe5}{farbe6}{farbe7} + +\node at (45:4) [above right] {$A$}; + +\clip (-7,-4.4) rectangle (0,4.8); +\foreach \k in {1,...,5}{ + \pgfmathparse{20*(3-\k)} + \xdef\c{\pgfmathresult} + \pgfmathparse{90+(\k-0.5)*\s} + \xdef\a{\pgfmathresult} + \pgfmathparse{\a-180} + \xdef\b{\pgfmathresult} + \draw[->] (-7.5,0) to[out={\c},in={180+\b}] (\a:4); + %\node at (\a:4) [left] {$\b$}; +} +\end{scope} + +\def\pearl#1#2{ + \fill[color=#2] ($({90+(#1-0.5)*\s}:0.6)$) circle[radius=0.12]; + \draw[line width=0.1pt] ($({90+(#1-0.5)*\s}:0.6)$) circle[radius=0.12]; +} + +\def\kette{ + \draw (0,0) circle[radius=0.6]; + \pearl{1}{farbe1} + \pearl{2}{farbe2} + \pearl{3}{farbe3} + \pearl{4}{farbe4} + \pearl{5}{farbe5} + \pearl{6}{farbe6} + \pearl{7}{farbe7} + \pearl{0}{farbe8} +} + +\begin{scope}[xshift=-4.5cm] +\fill[color=white] (-1.5,-2.5) rectangle (1.5,2.5); +\draw (-1.5,-2.5) rectangle (1.5,2.5); +\kette +\node at (-1.5,2.5) [below right] {$G$}; +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index 600336c..b066969 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -52,10 +52,10 @@ Inverse kann zum Beispiel als die inverse Matrix mit dem Gauss-Algorithmus berechnet werden. In einem zweiten Schritt zeigen wir dann, dass man die Rechnung noch etwas vereinfachen kann, wenn man in Polynomringen arbeitet. -Schliesslich zeigen wir dann im -Abschnitt~\ref{buch:subsection:zerfaellungskoerper}, wie man -den Prozess iterieren kann und so für beliebige Polynome immer einen -Körper finden kann, der alle Nullstellen enthält. +%Schliesslich zeigen wir dann im +%Abschnitt~\ref{buch:subsection:zerfaellungskoerper}, wie man +%den Prozess iterieren kann und so für beliebige Polynome immer einen +%Körper finden kann, der alle Nullstellen enthält. Wir beginnen in Abschnitt~\ref{buch:subsection:irreduziblepolynome} damit, die Polynome, die für die Konstruktion in Frage kommen, etwas genauer zu charakterisieren. @@ -608,7 +608,17 @@ $J$ mit $I\subset J\subset R$ entweder $I=J$ oder $J=R$ gilt. Die Ideale $p\mathbb{Z}\subset \mathbb{Z}$ sind maximal genau dann, wenn $p$ eine Primzahl ist. -TODO: XXX Begründung +Ist nämlich $p=n_1n_2$ eine Faktorisierung, dann ist +$\mathbb{Z}\supset n_1\mathbb{Z} \supset p\mathbb{Z}$ +und $n_1\mathbb{Z}$ ist ein grössers Ideal als $p\mathbb{Z}$, +d.~h.~$p\mathbb{Z}$ ist nicht maximal. + +In $\mathbb{Z}$ sind alle Ideale von der Form $n\mathbb{Z}$. +Wenn es also ein Ideal $I\supset p\mathbb{Z}$ gibt, welches +$p\mathbb{Z}$ echt enthält, dann gibt es $n\in\mathbb{Z}$ derart, +dass $n\mathbb{Z} \subset p\mathbb{Z}$. +Dies ist gleichbedeutend damit, dass $n$ ein echter Teiler von $p$ +ist, also ist $p$ keine Primzahl. \end{beispiel} \begin{satz} @@ -616,6 +626,23 @@ Der Ring $R/I$ ist genau dann ein Körper, wenn $I$ ein maximales Ideal ist. \end{satz} \begin{proof}[Beweis] +Nehmen wir zunächst an, dass $I$ ein maximales Ideal ist. +Damit $R/I$ ein Körper ist, muss jedes von $0$ verschiedene Element +eine multiplikatives Inverses haben. +Sei als $a\in R\setminus I$, dann ist $a+I$ ein von $0$ verschiedenes +Körperelement. +Die Menge $Ra+I$ ist dann ein Ideal von $R$, welches $I$ echt enthält. +Weil $I$ maximal ist, ist $Ra+I=R$, also gibt es ein Element $b\in I$ +derart, dass $ab+I=1+I$, d.~h.~$b+I$ ist das gesuchte multiplikative +Inverse. + +Sei nun umgekehrt $R/I$ ein Körper und $J\supset I$ sei ein Ideal, +welches $I$ echt enhält. +Sei $a\in J\setminus I$. +Da $R/I$ ein Körper ist, ist $a+I$ invertierbar, es gibt also ein +$b\in R$ mit $ab+I=1+I$. +Da $a\in J$ folgt $Ra\subset J$. +Andererseits ist $1\in Ra$, also ist $J=R$ und das Ideal $J$ ist maximal. \end{proof} Ein irreduzibles Polynom $m\in\Bbbk[X]$ erzeugt ein maximales Ideal, @@ -894,10 +921,3 @@ Dieser Spezialfall ist für die praktische Anwendung in der Kryptographie von besonderer Bedeutung, daher wird er im In Kapitel~\ref{buch:chapter:kryptographie} genauer untersucht. -\subsection{Zerfällungskörper -\label{buch:subsection:zerfaellungskoerper}} -XXX TODO - - - - |