\documentclass[a4paper,DIV15,BCOR12mm (new)]{article} \newcounter{chapter} \setcounter{chapter}{3} \usepackage{ztheo}
\author{Joachim Breitner} \title{Kongruenzen und Restklassenringe}
\begin{document} \maketitle
In diesem Kapitel betrachten wir entweder $R=\MdZ (new)$ oder $R=KX (new)$, wobei $K$ ein Körper ist.
\section*{Grundbegriffe}
In den betrachteten Ringen gibt es eine eindeutige Restwahl: In $R=\MdZ (new)$ ist die Division mit Rest $a=qm+r$ mit $0\le r < |m|$. Andere Restwahl wäre etwa $a=qm+r'$ mit $-\frac {|m|}2 < r' \le \frac{|m|}2$. Es besteht folgender Zusammenhang: $$r' = \begin{cases} r, & 0\le r\le \frac{|m|}{2} \\ r-|m|,& \frac{|m|}2 < r \le |m|\end{cases}$$ %
In $R=KX (new)$ haben wir $a=qm+r$ mit $\grad r < \grad m$.
Diese Reste sind eindeutig: Haben wir $a=qm+r=\tilde q m + \tilde r$ mit $0\le r,\tilde r, |m|$. Dann ist $(q-\tilde q)m=\tilde r -r \implies |m|\big|\tilde r - r$. Annahme: $q-\tilde q \ne 0 \implies |\tilde r - r| \ge m$, Wid. Also ist $q=\tilde q$ und $r = \tilde r$. Der Beweis für $R=KX (new)$ funktioniert ähnlich.
\begin{definition}[Gauß für $R=\MdZ (new)$] $m,a,b, \in R$ \begin{enumerate} \item \[ a \equiv b \mod m \text{ (lies $a$ kongruent $b$ modulo $m$} \] \[ \equizu a \mod m = b\mod m \] Gauß schreibt "`Zwei Zahlen heißen kongruent mod $m$, wenn sie bei Division durch $m$ den selben Rest lassen."' \item $\overline a := \{ b \in R| b \equiv a \mod m \}$ heißt Restklasse modulo $m$. \item $\overline R := R/mR := \{\overline a | a \in R\}$ heißt Restklassenring modulo $m$. \end{enumerate} \end{definition}
Warum ist Letzeres ein "`Ring"'? Der Dozent führt einen schönen Beweis durch Aufwickeln einer Schnur auf einer Tesa-Rolle durch.
\begin{beispiel} $\MdZ (new)/2\MdZ (new) = \{ \overline 0, \overline 1\}$ mit $\overline 0 = \{0, \pm 2, \pm 4, \ldots \}$ (die geraden Zahlen) und $\overline 1 = \{\pm 1, \pm 3, \ldots \}$ (die ungeraden Zahlen). Aus der Schule sind folgende Regeln bekannt: \begin{enumerate} \item $\overline 0 + \overline 0 = \overline 0$, "`gerade + gerade = gerade"' \item $\overline 0 + \overline 1 = \overline 1$, "`gerade + ungerade = ungerade"' \item $\overline 1 + \overline 1 = \overline 0$, "`ungerade + ungerade = gerade"' \end{enumerate} \end{beispiel}
\begin{bemerkung} \[ \text{(i) } a\equiv b \mod m \iff \text{ (ii) } \overline a = \overline b \iff \text{ (iii) }m|a-b\] Merke: Kongruenz ist Gleichheit der Restklassen.
$\overline{qm} = \overline 0$. Die Idee: In $\overline R$ wird alles durch $m$ teilbare als "`unwesentlich"' angesehen und durch $0$ ersetzt. \end{bemerkung}
\begin{beweis} $(i) \iff (ii)$: Kongruenz mod $m$ ist Offensichtlich eine Äquivalenzrelation auf $R$. $\overline a$ ist die Äquivalenzklasse von $a$. Lineare Algebra: Zwei Elemente sind genau dann äquivalent, wenn die zugehörigen Äquivalenzklassen überstimmen.
$(i) \implies (iii)$: $r = a \mod m = b\mod m \implies a = qm + r, b= q'm + r$ (Division mit Rest) $\implies a - b = (q-q')m \implies m | a-b$ \end{beweis}
Um mit Restklassen zu rechnen, brauchen wir folgende Definitionen: \begin{definition} Jedes $b\in \overline a$ heißt Vertreter der Klasse $\overline a \in \overline R$. Die Idee ist, die Operationen $+$ und $-$ vertreterweise zu definieren. Wir haben also: \[ (\overline R, +, \cdot)\text{ mit } \overline a + \overline b := \overline {a+b},\ \overline a \cdot \overline b = \overline{a\cdot b} \] \end{definition}
Zu zeigen: Die Definition ist vertreterunabhängig, also : $\overline a = \overline {a'} \implies \overline {a+b} = \overline {a'+b} \text{ und } \overline {a\cdot b} = \overline {a'\cdot b}$. Das ist klar: \begin{align*} \overline a = \overline a' \iff &m|a-a' = a+b - (a'+b) \implies \overline {a+b} = \overline {a'+b} \\ &m|a-a' \implies m|(a-a')b = ab - a'b \implies \overline {ab} = \overline {a'b} \end{align*}
\begin{bemerkung} $e\in R^\times, m \in R \implies R/mR = R/emR$ (da $m|x \iff em|x$). Ohne Beschränkung der Allgemeinheit kann man $m$ also normiert annehmen.
$m=0$, dann $a\mod m = b\mod m\iff a=b$, also $\overline a = \{a\} \text{\glqq}=\text{\grqq} a$. Also: $R/oR = R$ und $R/eR = R/R = \{\overline 0\}$ ("`Nullring"') \end{bemerkung}
Diese uninteressanten Fälle werden meist beiseite gelassen.
\begin{satz}Restklassenring-Satz (new) Sei $R$ ein euklidischer Ring, $m\in R$. \begin{enumerate} \item ($\overline R = R/mR, +, \cdot)$ ist ein Ring \item $\overline R^\times = \{\overline a \in \overline R| \ggt(a,m) = 1\}$
Zusatz: Zu $\overline a \in \overline R^\times$. Kann ${\overline a}^{\,-1}$ effektiv mit Euklids Algorithmus berechnet werden. \end{enumerate} \end{satz}
\begin{definition} $\overline a \in \overline R^\times$ heißt eine prime Restklasse modulo $m$, $\overline R^\times$ heißt prime Restklassengruppe modulo $m$. (Sprachlich besser wäre eigentlich: Gruppe der zu m relativ primen Restklassen) \end{definition}
\begin{beweis} \begin{enumerate} \item Alle Ringaxiome vererben sich von den Vertretern auf die Klassen. $\overline a + \overline b = \overline {a+b} = \overline {b+a} = \overline b + \overline a \implies$ $(\overline R,+)$ ist kommutativ. $0 := 0_{\overline R} = \overline 0$, da $\overline a + \overline 0 = \overline (a+0) = \overline a$. $1_{\overline R} = \overline 1$ ebenso.
Assoziativität der Addition: $(\overline a+ \overline b) + \overline c = \overline {a+b} + \overline c = \overline {(a+b) +c } = \overline {a + (b+c)} = \overline a + \overline {b+c} = \overline a + (\overline b + \overline c)$, Assoziativität der Multiplikation und Distributivgesetzt analog. \item $\overline a \in \overline R^\times \equizunach{Def.} \exists x \in R: \overline x \overline a = 1_{\overline R} = \overline 1 \iff 1 \equiv ax \mod m \iff \exists q \in R: 1 =ax + qm \implies \ggt(n,m)=1$, (da normal).
Der LinKom (new)-Satz \ref{satz:LinKom (new)} liefert: $d=\ggt(a,m) \implies \exists x,y\in R: d=ax+by$. Diesen Satz dürfen wir anwenden, da $R$ euklidisch ist. Wir wenden ihn mit $d=1, q=y$ an und erhalten $1=ax+qm$, wobei $x$ durch Euklids Algorithmus geliefert wird. $\implies \overline 1 = \overline a \overline x + \overline q \overline m = \overline a \overline x$. Resultat: $\overline a ^{\,-1} = \overline x$ mit dem so berechnetem $x$. \end{enumerate} \end{beweis}
\begin{folgerung} Ist $m\in \MdNp (new)$, dann gilt für Eulers Funktion $\varphi$: \[ \varphi(m) = \#\{R/mR\}^\times \] \end{folgerung}
Der Grund ist dass $R/mR = \{\overline 0, \ldots, \overline {m-1}\}$ und $(R/mR)^\times = \{\overline r | 0 \le r < m, \ggt(r,m)=1\}$, derer es $\varphi(m)$ gibt.
Im Allgemeinen ist $\overline R$ nicht integer. Beispielsweise in $\MdZ (new)/4\MdZ (new)=\overline R$ gilt: $\overline 2 \cdot \overline 2 = \overline 4 = 0_{\overline R} = 0$, aber $\overline 2 \ne 0$
\begin{folgerung} Falls $m$ unzerlegbar (also $m$ Primzahl oder -polynom). Dann gilt: $R/mR$ ist ein Körper. \end{folgerung}
Speziell: \begin{enumerate} \item $\MdF (new)_p := \MdZ (new)/p\MdZ (new)$, $p\in\MdP (new)$ ist Körper mit $p$ Elementen. \item Ist $f\in KX (new)$, f irreduzibel, so ist $KX (new)/f\cdot KX (new) = \overline R$ ein Körper. \end{enumerate}
Grund: $m$ sei unzerlegbar. Dann $\overline a \in \overline R,$ $\overline a\ne 0 = \overline 0 \iff m\not|a \implies \ggt(m,a) = 1$ ($1,m$ sind die einzigen normierten Teiler von $m$!) $\implies a \in \overline R^\times$. Es gilt also $\overline R^\times = \overline R\setminus\{0\} \implies \overline R$ ist Körper.
$\overline R = R/mR \ni \overline a = a + Rm := \{a + qm \big| q \in R\}$ Restklasse von a.\\ Rechne in $\overline R$: \textbf{Idee}: Kodiere die Restklasse $\overline a$ durch den Vertreter $a \mod m$.\\
Beliebige Vertretersysteme (ohne Einschränkung $m \in \MdN (new)_+, m > 1)$ \begin{itemize}
\item[] \underline{R = $\MdZ$}: \\$\text{Versys}_m = \{0,1,...,m-1\}$ "`\emph{System Betrag kleinster positiven Reste}"' oder $\text{Versys}_m =\{v \in \MdZ \big| - \frac{m}{2} < r \le \frac{m}{2}\}$ "`\emph{Symmetrisches Restsystem}"'
\item[] \underline{R = $K[X]$}: \\$\text{Versys}_m = \{f \in K[X] \big| \text{Grad } f < \text{ Grad } m\}$ (Grad $m > 0$)
\end{itemize}
\textbf{Klar}: \[\begin{array}{rcl}
\text{Versys}_m & \longrightarrow & R/mR \text{ (Ist bijektiv)}\\
r & \longmapsto & \overline r\\
a & \longmapsto & \overline a \mod m \text{ (Umkehrung)}
\end{array}
\]
Transportiere die Struktur $(\text{Versys}_m, \oplus, \odot)$, wobei gilt: \[
r \oplus s := r+s \mod m \qquad r \odot s := rs \mod m
\] Klar, $r \mapsto \overline r$ ist ein Ringisomorphismus.
Vorzug bei $R = \MdZ (new)$: \begin{itemize}
\item[] $r+s \mod m$ mit $1$-Addition: Zahlen $< 2m$
\item[] $r\cdot s$: Zahlen $<m^2$
\item[] ($m \mod \frac{m^2}{4}$ bei symmetrischen Resten)
\end{itemize}
Vorzug bei $R = KX (new)$: \begin{itemize}
\item[] Ist $n = \text{Grad }f$, so ist $\text{Versys}_m$ ein $K$-Vektorraum der Dimension $n$ (Basis z.B.: $1, X, X^2, ..., X^{n-1}$)
\item[] $\text{Grad }f < m$, $\text{Grad }g < m \implies \text{ Grad } (f+g) < m \implies f \oplus g = f + g \implies \oplus = +$
\item[] $\text{Versys}_m$ enthält $K$ als Teilkörper (konstante Polynome), da:\\
$\alpha, \beta \in K \subset K[X] \implies \alpha \odot \beta = \alpha \beta \mod m = \alpha\beta$
\end{itemize}
\begin{folgerung}
$\overline R = K[X]/mK[X]$ ist ein $K$-Vektorraum der $\text{dim }n = \text{ Grad }m$ mit Basis $1, \overline X, \overline X^2, ..., \overline X^{n-1}$. Identifiziert man $\alpha \in K$ mit der Restklasse $\overline \alpha$, so enthält $\overline R$ den Körper $R$.
\end{folgerung}
\begin{folgerung}
Ist $m \in \MdF_p[X] = R$ irreduzibel, so ist $R/mR = \overline R$ ein Körper mit $q = p^n$ ($n = \text{ Grad }m$) Elementen!\\
\textbf{Grund:} $\MdF_p$-Basis ist $1, \overline X, \overline X^2, ... , \overline X^{n-1}$.\\
$\overline R = \{\alpha_0 \cdot 1 + \alpha_1 \overline X +... + \alpha_{n-1} \overline X^{n-1} \big| \alpha_0,...,\alpha_{n-1} \in \MdF_p\}$ mit $\# \overline R = p^n$
\end{folgerung}
Zum Rechnen in $\overline R$ wird empfohlen $\overline \alpha \in \MdF (new)_p$ durch $r = a \mod p$ zu ersetzen, mit $r \in \text{Versys}_p$. $f \in \text{Versys}_pX (new)$ hat die Form $f = \sum_{i=0}^n c_iX^i$, $c_i \in \text{Versys}_p$. \\ Bei der Bestimmung von $f+g, f\cdot g$ ist bei allen Rechnungen mit Koeffizienten $c_1,...,c_n$, $+$ durch $\oplus$ und $\cdot$ durch $\odot$ zu ersetzen. Man kann auch $f+g, f\cdot g$ in $\MdZ (new)X (new)$ berechnen und dann zu allen Koeffizienten die Reste $\mod p$ nehmen.
\begin{beispiel}
$\MdF_3[X]$, $\MdF_3 =\{\overline 0, \overline 1, \overline 2\}, \text{ Versys}_3 = \{0,1,2\}$\\
$\begin{array}{rcl}
\underbrace{(X^2 + 2X + 1)}_{\mathclap{(\text{= } \overline 1 \cdot X^2 + \overline 2 \cdot X + \overline 1 \text{ in } \overline R[X])}} \cdot (2X + 1) & = & 2X^3 + \underbrace{2 \odot 2}_{\mathclap{=1 \text{ in } \MdZ[X]}}X^2 + 2X + X^2 + 2X + 1\\
&=&2X^3 + 4X^2 + 2X + X^2 + 2X + 1\\
&=&2X^3 + \underbrace{5}_{\mathclap{2 \mod 3}}X^2 + \underbrace{4}_{\mathclap{1 \mod 3}}X + 1\\
&=&2X^3 + (1 \oplus 1)X^2 + (2 \oplus 2)X + 1\\
&=&2X^3 + 2X^2 + X + 1
\end{array}$
\end{beispiel}
\begin{beispiel}
$\MdF_4 = \{\underbrace{0, 1}_{\MdF_2}, \underbrace{\overline x}_{=: \varrho}, \overline x + 1\}$, wenn $m$ irreduzibel in $\MdF_2[X]$, $\text{Grad }f = 2$\\ $X^2 + 1 = (X + 1)^2$ $(= X^2 + \underbrace{\overline 2}_{=0}X + 1 = X^2 + 1 \text{ in } \MdF_2[X])$\\
$X^2 + X + 1$ ist irreduzibel. (Alle Polynome vom $\text{Grad }1$ sind $X, X+1, X^2, X(X+1),(X+1)^2 = X^2 + 1$ sind von $m$ verschieden $\implies$ irreduzibel)\\
$\MdF_4 = \{0,1,\varrho, \varrho + 1\}$, $\varrho^2 = ?$\\
$(\overline X)^2 = \underbrace{\overline{X^2 \mod m}}_{\in \text{ Versys}_m} = \overline{X + 1} = \overline X + 1 = \varrho + 1$\\
$X^2 -1\cdot (X^2 + X + 1) = -X - 1 = X + 1$ in $\MdF_2[X]$\\
Rechenregel: $\varrho^2 = \varrho +1 \implies $ Multiplikationstafel
\end{beispiel}
\begin{bemerkung}
\text{ }
\begin{itemize}
\item $R \to \overline R = R/mR$, $\kappa: a \mapsto \overline a = \kappa(a)$, so ist $\kappa$ surjektiver Ringhomomorphismus. $\kappa(a+b) = \overline a + \overline b = \overline{a+b} = \kappa(a+b)$
\item Ist $R$ ein Ring und $z \in \MdZ$, so definiert man:
\[z \cdot \varrho := sgn(z)\underbrace{(\varrho + \varrho + ... + \varrho)}_{|z|-\text{Stück}}\]
\end{itemize}
\end{bemerkung}
\begin{beispiel}
$\overline R = \MdZ/m\MdZ, z \in \MdZ$\\
$z\overline a = \overline{za}$ (leicht selbst nachzuweisen)\
$m \cdot 1_{\overline R} = m \cdot \overline 1 = \overline m = 0_{\overline R}$
\end{beispiel}
\textbf{Rechenregeln:} $z, z_1, z_2 \in \MdZ (new), \varrho, \varrho_1, \varrho_2 \in R$ \begin{itemize}
\item[] $(z_1 + z_2)\varrho = z_1\varrho + z_2\varrho$ \item[] $z(\varrho_1 + \varrho_2) = z\varrho_1 + z\varrho_2$ \item[] $(z_1z_2)\varrho = z_1(z_2\varrho)$ \item[] $z(\varrho_1\varrho_2) = (z\varrho_1)\varrho_2 = \varrho_1(z\varrho_2)$ (Beweis leicht)
\end{itemize}
Für $f \in \MdZ (new)X (new), \overline a \in \MdZ (new)/\MdZ (new) m$ ist definiert ($f = \sum_{i=0}^n z_iX^i$): \[f(\overline a) = \sum_{i=0}^nz_i\overline a^i \in \overline R \text{ } (= \sum_{i=0}^n\overline{z_ia^i} = \overline{f(a)}\] Ergebnis: $f(\overline a) = \overline{f(a)}$
\section{Zyklische Gruppen}
\textbf{Aufgabe:} Berechne $3^{10^{500}} \mod \underbrace{167}_{=:p}$ (Rechne in $\text{Versys}_{167}$ !)
\textbf{Mathematische Hilfsmittel:} Ordnung eines Gruppenelements.
\begin{definition}
Sei $G$ eine (ohne Einschränkung multiplikative) endliche Gruppe, $x \in G$. (Das neutrale Element werde mit $1 = 1_G$ bezeichnet)
\begin{itemize}
\item[(i)] $\ord(x) = \min \{n \in \MdN_+ \big| x^n = 1\}$ heißt "`\emph{Ordnung von x}"'
\item[(ii)] $\#G$ heißt "`\emph{Ordnung von G}"'
\end{itemize}
\end{definition}
\begin{bemerkung}
$\ord(x)$ existiert, da $n > m, n,m \in \MdN_+$ vorhanden sind mit $x^n = x^m$, da $G$ endlich. $\implies x^{n-m} = 1$. In allgemeinen Gruppen kann sein $\{n \in \MdN_+ \big| x^n = 1\} = \emptyset$, dann schreibt man $\ord(x) = \infty$
\end{bemerkung}
\begin{satz}Elementordnungssatz (new)
Sei $G$ eine endliche Gruppe, $x \in G$, $m, n \in \MdZ$. Dann gelten:
\begin{itemize}
\item[(i)] $x^m = x^n \iff m \equiv n \mod \ord(x)$\\
Insbesondere $x^m = x^{m \mod \ord(x)}$ und $\mod x^m = 1 \iff \ord(x) \big| m$
\item[(ii)] $x^{\# G} = 1$ (d.h. nach (i) $\ord(x) \big| \# G$)
\item[(iii)] $\ord(x^m) = \frac{\ord(x)}{\ggt (m, \ord(x))}$
\end{itemize}
\end{satz}
\textbf{Anwendung}: \begin{itemize}
\item[] \underline{Satz von Euler:} Sei $m, x \in \MdZ, m > 0, \ggt (x,m) = 1, \varphi$ sei die Eulersche Funktion. Dann gilt: $x^{\varphi(m)} \equiv 1 \mod m$
\item[] \underline{(Kleine) Satz von Fermat:} Sei $p \in \MdP, x \in \MdZ$. Dann gilt: $x^p \equiv x \mod p$
\end{itemize}
\textbf{Zum Satz von Euler:}\\ $G = (R/Rm)^\times, \# G = \varphi(m)$. $\overline x \in G \iff \ggt(x,m) = 1$. Elementordnungssatz (ii) $\implies \overline 1 = 1_g = \overline x^{\# G} = \overline x^{\varphi(m)} = x^{\varphi(m)} \iff 1 \equiv x^{\varphi(m)} \mod m$
\textbf{Zum Satz von Fermat:}\\ $\varphi(p) = p-1$. Aussage klar, wenn $p \big| x (x \equiv 0 \equiv xp)$. $p \nmid x \implies \ggt(p,x) = 1 \implies \overline x^{p-1} = \overline x^{\# G} = \overline 1 \implies \overline x^p = \overline x \implies x^p \equiv x \mod p$
\begin{beweis}Elementordnungssatz (new) Sei $x\in G$, $\ord(X) =: l$. \begin{enumerate} \item $x^m = x^n \iff x^{m-n}= 1 = 1_G \iff 1= x^{ql+r} = (w^l)^q\cdot x^r = 1^q\cdot x^r = 1x^r = x^r$ (Falls $r\ne0$, so haben wir einen Widerspruch zur Minimalwahl von $l$) $\iff r=0 \iff l\mid m-n \iff m \equiv n \mod l$.
Insbesondere: $x^m=1 \iff l \mid m$, $x^n = x^{n\mod l}$ \item $x^{\#G} = 1$. Dies wird in dieser Vorlesung nur für kommutative $G$ benötigt und bewiesen. Betrachte die Abbildung $G\to G$, $x \mapsto y\cdot x$. Sie ist bijektiv (die Umkehrabbildung ist $y\mapsto y x^{-1}$), also $\{y \mid y\in G\} = G = \{yx \mid y\in G\}$. \[ \prod_{y\in G}y =\prod_{y,x\in G} (yx) = \prod_{y\in G} y \cdot x^{\#G} \implies x^{\#G} = 1 \]
Also laut (1): $\ord(x) \mid \#G$
\item $\ord(x^m)=k \implies 1= (x^m)^k = x^{mk} \folgtnach{(1)} l \mid mk$. Sei $d=\ggt(m,l) \implies \frac{l}{d} \mid \frac{m d} \cdot k \folgt \frac l d \mid k$. Warum sind $\frac l d$ und $\frac md$ relativ prim? $d = \ggt(m,l)= d\cdot \ggt(\frac m d, \frac l d) \folgt \ggt(\frac m d, \frac l d) = 1$. Aber $k \mid \frac l d$ wegen $(x^m)^{\frac l d} = x^{l\cdot \frac md} = 1^{\frac m d} = 1$, $k= \ord(x^m)$ nach (1).
Ergebnis: $k = \frac l d = \frac {\ord(x)} {\ggt(\ord(x),m)}$
\end{enumerate} \end{beweis}
\subsubsection*{Hilfestellungen zur Berechnung von $\ord(x)$}
\begin{bemerkungen} \begin{enumerate} \item $\ord(a)\mid\#G$ (\emph{wirklich $a$?}) \item Sei $x^d=1$. Dann gilt: $d = \ord(x) \iff \forall p\in\MdP (new)$ mit $p\mid d$: $x^{\frac dp} \ne 1$. \end{enumerate} \end{bemerkungen} \begin{beweis}[Der Bemerkung (ii)] "`$\Longrightarrow$"': Klar
"`$\Longleftarrow$"': Sei $x^d=1$, $x \ne \ord(x)$. Nach (1): $\ord(x)\mid d \implies \exists p\in\MdP (new): \ord(x) \mid \frac dp \folgt x^{\frac d p } = 1$ \end{beweis}
Zur Berechnung von $x^n$: Naive rekursive Berechnung: $x^{j+1} = x^j\cdot x$. Hier hätten wir $n$ Produkte zu berechnen! Westentlich bessere Methode: Stelle $n$ binär da: $n = \sum_{i=0}^t c_i \cdot 2^i$, $c_t\ne 0$, $c_i\in\{0,1\}$. Bezeichnung $n=(c_t,c_{t-1},\ldots,c_0)_2$ mit den Binärziffern $c_j$. \[ x^n = x^{ \sum_{i=0}^t c_i \cdot 2^i} = \prod_{i=0}^t \left(x^{2^i} \right)^{\mathrlap{c_i}} = \prod_{\mathclap{i=0,\ c_i\ne 0}}^t x^{(2^i)} \] Rekursiv: $x^{2^0} = x^1 = x$ und $x^{2^{i+1}} = (x^{2^{i}})^2$. $t$ ist etwa $\log_2 n$, man hat ungefähr $2\cdot\log_2 n$ Produkte zu berechnen.
\begin{beispiel} $G=\MdF (new)_9^\times$, $\#G = 9-1 = 8$. Mögliche $\ord(\alpha)$ für ein $\alpha\in G$: 1,2,4, oder 8. \begin{align*} \ord(\alpha) = 1 &\iff \alpha = 1 \\ \ord(\alpha) = 2 &\iff \alpha \ne 1, \alpha^2 = 1 \iff \alpha = -1_G = -1 \\ \ord(\alpha) = 4 &\iff \alpha^4 =1 , \alpha^2 \ne 1 \text{ (d.h. $\alpha \ne \pm 1$)} \\ \ord(\alpha) = 8 &\iff \alpha^4 \ne 1 \end{align*}
$\MdF (new)_9 = \MdF (new)_3X (new) / m\cdot\MdF (new)_3X (new)$, $\ord(m)=2$, $m$ irreduzibel. Beispielsweise ist $X^2+1$ in $R=\MdF (new)_3X (new)$ irreduzibel.
$\MdF (new)_9$ hat $\MdF (new)_3$-Basis $1;\overline x$. $\MdF (new)_9 = \{\underbrace{0,1,-1}_{\mathclap{\MdF (new)_3=\text{Versys}_3}},\ldots \}=\{a+b\overline x\mid a,b\in\MdF (new)_3\}$
$m=X^2+1\equiv 0 \mod m \folgt X^2 \equiv -1 \mod m \folgt \overline X^2 = -1 = -1_{\MdF (new)_9} = -1_{\MdF (new)_3} \folgt \overline X^4 = (-1)^2 = 1 \folgt \ord(\overline X)=4$.
$(\overline X+1)^2 = \overline X^2 + 2\overline X +1 = -1 + 1 + 2X = -X \ne 1$, $(\overline X+1)^4 = (-\overline X)^2 = \overline X^2 = -1 \folgt {\ord(\overline X+1)=8}$ \end{beispiel}
Zurück zum Problem $3^{(10^{500})} \mod 167$, $167\in\MdP (new)$. $G=\MdF (new)_{167}$, $\#G=\varphi(167) = 166 = 2\cdot 83$, also gilt $\ord(n) \in \{1,2,83,166\}$.
Laut Ordnungsatz: $3^{10^{500}} \equiv 3^{10^{500} \mod \ord(\overline 3)}$.
Wir brauchen $\ord(3)$: $\overline 3 ^2 = \overline 9 \ne 1_G \folgt \ord(\overline 3)\ne 1,2$, $\ord(\overline 3) = 83 \iff \overline 3 ^{83} = 1_G = \overline 1$. $83 = (1010011)_2=64+16+2+1$. Tabelle: $3^{2^0}$ in $\MdF (new)_{167}$ ist 3, $3^{2^1}$ in $\MdF (new)_{167}$ ist $3^2=9$, $3^{2^2}$ in $\MdF (new)_{167}$ ist $9^2=81$, $3^{2^3}$ in $\MdF (new)_{167}$ ist $81^2 = 6651 = 30\cdot 167+48\equiv 48$, $3^{2^4}$ in $\MdF (new)_{167}$ ist $48^2 \equiv 133$, $3^{2^5}$ in $\MdF (new)_{167}$ ist $133^2 = 17629 \equiv 154$, $3^{2^6}$ in $\MdF (new)_{167}$ ist $154^2 = \equiv 2$. Also: $\overline 3 ^{83} =\overline 3 \cdot \overline 9 \cdot \overline{133} \cdot \overline 2\cdot \overline{7182} \cdot \overline{1} =1_G$. Ergebnis: $\ord(\overline 3)=83$.
$3^{10^{500}} = 3^{10^{500} \mod 83}$. Noch zu berechnen: $10^{500} \mod 83$. Man kann $\overline{10}$ in $\MdF (new)_{83}$ berechnen. Reicht auch $\overline{10}^{500} = 10^{500\mod \varphi(83)}$. $\varphi(83) = 82$, $500\equiv 8 \mod 82 \folgt 10^{500} \equiv 10^8 \equiv 23 \mod 83$
Also: $\overline 3 ^{10 ^{500}} = \overline 3 ^{23} = \overline{124}= \overline{-33}$ und somit $3^{100^{500}} = 124 \mod 167$
\begin{satz}Mersenne-Teiler-Satz (new) Es seien $p,q\in\MdP (new)$ mit $q \mid M_p = 2^p-1$. Dann gilt: $q\equiv 1 \mod p$ \end{satz}
\begin{beweis} $q\mid M_p \iff M_p = 2^p-1 \equiv 0 \mod q \iff \overline 2^p = 1$ in $\MdF (new)_q^\times=G \folgt \ord(\overline 2) = p$, da 1 nicht geht und $\ord(\overline 2)\mid p$ nach dem Ordnungsatz. $\ord(\overline 2) \mid \# G = \varphi(q) = q-1 \folgt q-1 \equiv 0 \mod p \folgt q \equiv 1 \mod p$ \end{beweis}
\paragraph{Bezeichnungen:} \begin{enumerate} \item $\langle x \rangle = \{1,x,x^2,\ldots,x^{l-1}\}$, ($l=\ord(x)$), heißt die von $x$ erzeugte zyklische Untergruppe von $G$. \item $G$ heißt zyklisch $\iff \exists x \in G: G=\langle x\rangle \iff \exists x \in G: \ord(x)=\#G$ \end{enumerate}
\begin{bemerkung} Die Abbildung $(\MdZ (new)/\MdZ (new) l,+)\to (\langle x\rangle ,\cdot)$ mit $\overline m \mapsto x^m$ ist ein Isomorphismus von Gruppen. \end{bemerkung} \section{Primitivwurzeln}
Vorbereitungen über $R=KX (new)$, $K$ ein Körper.
\begin{bemerkung} Sei $\alpha \in K$, $f\in R$, $\ord(f)>0$. Dann gilt: \[ 0 = f(\alpha) \iff X-\alpha \mid f \iff v_{X-\alpha}(f) > 0 \quad ( X-\alpha \in \MdP (new)_{R} )\] $v_{X-\alpha}$ heißt Vielfachheit der Nullstelle $\alpha$ von $f$. \end{bemerkung}
\begin{beweis} Division mit Rest: $f= q\cdot (X-\alpha) + r$. $\grad r < \grad (X-\alpha) = 1 \folgt r\in K$ (konstantes Polynom), insbesondere $r(\alpha) = r$. $f(\alpha) = q(\alpha)(\alpha-\alpha) + r(\alpha) = r $. Also: $r(\alpha) = 0 \iff {r = 0} \iff {X-\alpha \mid f}$ \end{beweis}
\begin{satz}Nullstellenanzahls-Satz (new) $f\in KX (new)$, $f\ne 0$, $n=\grad f$, so gilt: $f$ hat höchstens $n$ verschiedene Nullstellen in $K$. \end{satz}
\begin{beweis} $\alpha_1,\ldots,\alpha_l$ seien $l$ Nullstellen. $v_{X-\alpha_j}(f) > 0 \folgt \prod_{j=1}^l (X-\alpha_j) \mid f$, wegen ${v_{X-\alpha_i}(\prod_{j=1}^l(X-\alpha_j)) = 1}$ und ${v_{m}(\prod_{j=1}^l(X-\alpha_j)) = 0}$ für alle anderen $m\in \MdP (new)$ sowie $v_{X-\alpha_j}(f) \ge 1$. Daraus folgt: $l\le \grad f$ \end{beweis}
Der Spezialfall $K=\MdF (new)_p$ ergibt den
\begin{satz}[Satz von Lagrange] Sei $p\in\MdP (new)$, $f=\sum_{i=0}^n c_iX^n \in \MdZ (new)X (new)$. Es gibt ein $j\in\{0,\ldots,n\}$ mit $c_j\not\equiv 0 \mod p$. Dann fallen die "`Lösungen"' $x\in\MdZ (new)$ der Kongruenz \[ f(x) \equiv 0\mathrlap{ \mod p} \] in höchstens $n$ verschiedene Restklassen modulo $p$. \end{satz}
\begin{beweis} Der Satz ist eine Übersetzung des Nullstellenanzahls-Satzes auf Kongruenzen. Betrachte die $\overline {c_j} = \alpha _j \in \MdF (new)_p \folgt \exists j:\, \overline{c_j}\ne 0\folgt f=\sum_{i=0}^n \overline{c_j}X^j \ne 0$ in $\MdF (new)_pX (new)$, $\ord(f)\le n$. $f(x) = 0 \mod p \iff \overline{f(x)} = f(\overline x) = 0_{\MdF (new)_p}$. Es gibt höchstens $n$ Nullstellen $\overline x$, das heißt lösende Kongruenzklassen. \end{beweis}
$p\in\MdP (new)$ wird gebraucht, Aussage modulo $m$, $m\notin \MdP (new)$, im Allgemeinen falsch. Beispiele: $m=6$, $f=X^2+X$ hat in $\MdZ (new)/6\MdZ (new)$ die Nullstellen $\overline 0$, $\overline 2$, $\overline 3$, $\overline 5$. $m=9$, $f=X^2$ hat in $\MdZ (new)/9\MdZ (new)$ die Nullstellen $\overline 0$, $\overline 3$, $\overline {-3}$.
\begin{satz}Primitivwurzelsatz (new) Sei $K$ Körper, $G$ eine \emph{endliche} Untergruppe von $K^\times$. Dann ist $G$ zyklisch. Genauer gilt: $\#\{\alpha \in K| \ord(\alpha) = \#G \} = \varphi(\#G)$ ($\varphi$ die Eulersche Funktion) \end{satz}
\begin{bemerkung} Ist $\ord(\alpha)=\#G$, so heißt $\alpha$ primitive $\#G$-te Einheitswurzel, da $\alpha^{\#G}=1$, sozusagen $\alpha = \sqrt[\#G]{1}$. primitiv, da $\alpha^m=1$, wobei $\#G\mid m$. \end{bemerkung}
\paragraph{Spezialfälle} \begin{enumerate} \item $K=\MdF (new)_q$, also ein Körper mit $q<\infty$ Elementen. $G=\MdF (new)_q^\times=\MdF (new)_q\setminus\{0\}$, $\#G=q-1$. Nach dem Satz ist $F_q^\times$ zyklisch $\alpha$ mit $\langle \alpha\rangle=\MdF (new)_q^\times$ heißt primitives Element. \item Noch spezieller: $\MdF (new)_p = \MdZ (new)/p\MdZ (new)$ mit $p\in\MdP (new)$ besitzt $\varphi(p-1)$ primitive Elemente $\alpha = \overline w$, $(0\le w < p-1)$. Solve $w$ heißen Primitivwurzel modulo $p$. \end{enumerate}
\begin{beweis} Sei $l = \#G$, $G$ wie im Satz.
Für die $d\mid l$, $d\in\MdNp (new)$, sei $\lambda(d)=\#\{\alpha \in G\mid \ord(\alpha)=d\}$. Laut Elementordnungssatz gilt: $l = \sum_{d\mid l}\lambda(d) = \sum_{d\mid l} \varphi(d)$ (Lemma von Gauß). Man will zeigen: $\lambda(d)\le \varphi(d)$ $(*)$, denn dann muss gelten: $\forall d\mid l: \lambda(d)=\varphi(d)$, denn sonst würde gelten: $\sum_{d\mid l}\lambda(d) < \sum_{d\mid l} \varphi(d)$.
$(*)$ ist klar, wenn $\lambda(d) = 0$. Sei also $\lambda(d)\ne 0 \folgt \exists \alpha \in G: \ord(\alpha) = d$. Sei $A=\langle \alpha \rangle = \{1,\alpha,\alpha^2,\ldots,\alpha{d-1}\}$. Klar: $(\alpha^d)^d = 1 \folgt \alpha^j$ ist eine Nullstelle von $X^d-1$. Wegen $\#A = d$ sind das $d$ Nullstellen von $X^d-1$, also alle solche. $B=\{\beta \in G\mid \ord(\beta) = d \}$, dann $\beta^d = 1 \folgt \beta$ Nullstelle von $X^d-1\folgt \beta\in A$. $B\subseteq A$.
$\alpha^j\in B \iff \ord(\alpha^j) = d \folgt d= \ord(\alpha^j) = \frac{\ord(\alpha)}{\ggt(d,j)}$ (Elementordnungssatz) $\folgt \ggt(d,j) = 1 \folgt B\subseteq \{\alpha ^j \mid \ggt(d,j)=1, 0\le j \le d\}$. $\#B=\lambda(d)\le \#\{\alpha ^j \mid \ggt(d,j)=1, 0\le j \le d\} = \varphi(d)$
\end{beweis}
Der folgende Satz ist eine Anwendung des Primitivwurzelsatzes:
\begin{satz}[Eulers Quadratkriterium] Sei $\alpha\in\MdF (new)_q^\times$ ($\MdF (new)_q$ ein Körper mit $q$ Elementen, $2\mid q$). Dann gilt: \[ \alpha \text{ ist ein Quadrat in }\MdF (new)_q^\times \iff \alpha^{\frac{q-1}{2}} = 1 \] Anderenfalls gilt: $\alpha^{\frac{q-1}{2}} = -1$
Euler formuliert den Satz so: Sei $p\in\MdP (new)$, $p>2$, $n\in\MdZ (new)$, $p\mid m$. Dann existiert ein $x\in\MdZ (new)$ mit $x^2 \equiv m \mod p \iff m^{\frac{p-1}2} \equiv 1 \mod p$. Solche $m\mod p$ heißen quadratische Reste.
Wenn Kongruenz als Gleichung in $\MdF (new)_p = \MdZ (new)/p\MdZ (new)$ gelesen wird, so gilt: \[ \alpha = \overline x \text{ Quadrat in }\MdF (new)_p^\times \iff x \text{ quadratischer Rest modulo }p \] \end{satz}
\begin{beweis} Sei $\zeta$ eine Primitivwurzel (Existenz folgt aus dem Primitivwurzelsatz).
"`$\Longleftarrow$"': Sei $\alpha^{\frac{q-1}2} = 1$ und $\alpha = \zeta ^j$. $\zeta^{j\cdot\frac{q-1}2} = 1 \folgt q-1=\ord(\zeta)\mid j^{\frac{q-1}2} \folgt \frac j 2 \in \MdZ (new) \folgt 2 \mid j \folgt \beta = \zeta^{\frac j 2}$ zeigt den Satz: $\beta^2 = \zeta ^j = \alpha$
"`$\Longrightarrow$"': $\alpha$ Quadrat $\iff \exists \beta \in\MdF (new)_q: \alpha = \beta^2 \folgt \exists k\in\MdZ (new): \beta = \zeta^k$. $\alpha= \zeta^{2k} \folgt \alpha ^{\frac{q-1}2} = \zeta ^{(q-1)k} = 1$, da $\ord(\zeta) = q-1$
$\alpha^{\frac {q-1}2}$ ist Nullstelle von $X^2-1$. Alle Nullstellen sind $\{1,-1\}$. $1$ entfällt, also ist $\alpha^{\frac{q-1}2} = -1$ \end{beweis}
% Wer das verstanden hat darfs gerne umformulieren: Eulers Formulierung "`$m$ nicht quadratischer Rest"', auch "`quadratischer Nichtrest"'. $\ggt(m,p) = 1 \folgt m^{\frac{p-1}2} \equiv -1 \mod p$
\section{Zifferndarstellung nach Cantor}
In diesem Abschnitt seien $R=\MdZ (new)$ oder $R=KX (new)$, $K$ ein Körper.
Ausgangspunkt ist die Folge $\gamma=(m_0,m_1,m_2,\ldots)$, $m_j\in R$ mit $m>1$ bei $R=\MdZ (new)$ oder $\grad(m_j)>0$ bei $R=KX (new)$.
Definiere $M_0=1$, $M_k=m_0\cdot \ldots \cdot m_{k-1}$.
\begin{satz}Ziffernsatz (new) Jedes $n\in\MdNp (new)$ bzw. $n\in KX (new)$, $n\ne 0$ hat eine eindeutige Darstellung \[n = z_rM_r + z_{r-1}M_{r-1} + \cdots + z_1M_1 + z_0 \quad (*)\] wobei $r\in\MdN (new)$ und $0\le z_j < m_j$ bzw. $\grad(z_j) < \grad(m_j)$
\end{satz}
\paragraph{Bezeichnungen:} Die $z_j$ heißen $\gamma$-adische Ziffern und $(*)$ Zifferndarstellung (vorlesungs-spezifisch). Kurzbezeichnung: $n=(z_r,z_{r-1},\ldots,z_0)_\gamma$. Die Kommata dürfen bei Eindeutigkeit weggelassen werden.
Spezialfall: $m_0=m_1=m_2=\cdots=:m$ gibt Zifferndarstellung $n=z_rm^r + z_{r-1}m^{r-1}+\cdots+z_0 = (z_r,\ldots,z_0)_m$ heißt $m$-adische Darstellung von $n$.
Speziallbenennungen:\\ \begin{tabular}h (new){r|l|l|l} $m$ & Zifferndarstellung & Ziffern & \\ \hline 10 & Dezimaldarstellung & 0,1,\ldots,9 & bei Menschen beliebt\\ &&& (10 Finger) \\ 2 & Binär oder dyadisch & 0,1 & bei Comptern beliebt \\ &&& (0,1 gut realisierbar) \\ 8 & Oktaldarstellung & 0,\ldots,7 & \\ 16 & Hexadezimal & 0,\ldots,9,A,B,C,D,E,F & Speicherverwaltung \\ &&& im Rechner \\ \end{tabular}
\begin{beispiel} \begin{align*} (A8C)_{16} &= 10\cdot 16^2 + 8\cdot 16 + 12\cdot 1 \\ &= 2700 := (2700)_{10} \\ &= (10101001100)_2 \\ &= (5214)_8 \end{align*} \end{beispiel}
$\gamma = (m_0, m_1, ...), m_j \in \MdZ (new)$ (bzw. $KX (new)$), $m_j > 1$ bzw. $\text{Grad } m_j > 0$\\ $M_0 = 1, M_k = m_0 \cdot ... \cdot m_{k-1}$
$\gamma$-adische Entwicklung von $n \in \MdN (new)_+$ bzw. $n \in KX (new), n \not= 0:$ \begin{equation}\label{eq:3.3star}
n = z_rM_r + z_{r-1}M_{r-1} + ... + z_1M_1 + z_0 \cdot 1
\end{equation} $\gamma$-adische Darstellung, wenn $0 \le z_j < m_j$ (bzw. $\text{Grad }z_j < \text{Grad }m_j$)
\begin{beweis}Ziffernsatz (new) Fall \eqref{eq:3.3star} vorliegt: Wegen $M_k \big| M_{k+1} \big| M_{k+2} \big| ...: \\ n \equiv z_{k-1}M_{k-1} + z_{k-2}M_{k-2} + ... + z_0 \mod M_k$
Speziell: $n \equiv z_0 \mod M_1 = m_0 \implies n-z_0 = n'm_0, n' \in \MdZ (new)$ bzw. $KX (new)$
\underline{Beweisidee:} Induktion nach $n$ bzw. $\text{Grad }n$ (hier nur $\MdZ (new), KX (new)$ fast genau so)
\underline{Behauptung:} Sei $n \in \MdZ (new)_+$. Dann existiert für alle $\gamma$'s dieser Art die $\gamma$-dische Darstellung \eqref{eq:3.3star}.\\ Induktion nach $n$:\\ Falls $n < m_0$, dann $z_0 = n, n = z_0M_0$ ist ($\star$)\\ Falls $n \ge m_0, z_0 = (n \mod m_0), n'$ aus $n - z_0 = n'm_0 (n' = \frac{n-z_0}{m_0})$. Klar $0 \le z_0 < m_0 \le n \implies 0 < n' < n$.\\ Induktionshypothese anwendbar auf $n'$ mit $\gamma' = (m_1', m_2', ...), m_j' = m_{j+1} (j \ge 0)$.
$\exists \gamma'$-adische Darstellung von $n'$:\\ $n' = z_{r'}'M_{r'}' + z_{r'-1}M_{r'-1}' + ... + z_1'M_1' + z_0' (r' \in \MdN (new), z_{r'}' \not= 0)$\\ $n \le z_j' < m_j' = m_{j+1} \implies n = n'm_0 + z_0 = z_{r'}'M_{r'+1} + ... + z_1'M_1 + z_0$\\ Das ist die gesuchte $\gamma$'-adische Darstellung von $n$ mit $r := r' + 1, z_j' = z_j + 1 (j = 0, ..., r')$ also $0 \le z_{j+1} = z_j < m_j' = m_{j+1}$\\ Dies ist ein Algorithmus, wenn die Abbildung $j \mapsto m_j$ berechenbar ist.
\underline{Eindeutigkeit:} Ebenfalls Induktion. $z_0$ muss $n \mod m_0$ sein. Induktionshypothese $n'$ eindeutig dargestellt $\implies$ Darstellung von $n$ eindeutig (Details: selbst!) \end{beweis}
\underline{Bemerkung:} Zur Berechnung von $(n_1 +/\cdot n_2)_\gamma$ aus $(n_1)_\gamma$ und $(n_2)_\gamma$ ähnliche Algorithmen wie für $()_{10}$.
\section{Simultane Kongruenzen}
\subsection{Prinzip des Parallelen Rechnens}
$R_j (j = 1,..., l)$ seien algebraische Strukturen gleicher Art mit gleichbezeichneten Verknüpfungen $\ast$, zum Beispiel: \begin{itemize}
\item[] Gruppen $\ast \in \{\cdot\}$
\item[] Abelsche Gruppen $\ast \in \{+\}$
\item[] Ringe $\ast \in \{+, \cdot\}$
\item[] Vektorräume $\ast \in \{+, \text{Skalarmultiplikation}\}$
\end{itemize}
Dann ist auch $S = \prod_{i=1}^lR_j = R_1 \times ... \times R_l$ eine algebraische Struktur mit Verknüpfungen (komponentenweise):\\ $S \ni (a_1,...,a_l), (b_1,...,b_l), a_j, b_j \in R_j$\\ $(a_1, ...,a_l) \ast (b_1,...,b_l) := (a_1 \ast b_1, ..., a_l \ast b_l)$\\ $\alpha(a_1, ..., a_l) := (\alpha a_1, ..., \alpha a_l)$ bei K-Vektorräumen.\\ Sind $_j$ Ringe/Gruppen/Abelsche Gruppen/Vektorräume, so \underline{auch $S$}.
\underline{Grund:} Alles vererbt sich von den Komponenten!\\ Zum Beispiel Ringe: $0_S = (0_{R_1}, ..., 0_{R_l}), 1_S = (1_{R_1}, ..., 1_{R_l})$, kurz: $0 = (0,...,0), 1 = (1,...,1)$, $-(a_1,...,a_l) = (-a_1, ..., -a_l)$\\ Zum Beispiel Assoziativität:\\ $((a_1,...,a_l) \ast (b_1,...,b_l)) \ast (c_1,...,c_l) = ((a_1 \ast b_1) \ast c_1, ..., (a_l \ast b_l) \ast c_l) = (a_1, ..., a_l) \ast ((b_1, ..., b_l) \ast (c_1, ..., c_l))$
\underline{\textbf{Warnung!}} Sind die $R_j$ Körper, so ist für $l > 1$, $S$ \underline{kein} Körper.\\ Zum Beispiel: $\underbrace{(1,0)}_{\not= 0} \cdot \underbrace{(0,1)}_{\not= 0} = (1 \cdot 0, 0 \cdot 1) = (0, 0) = 0$
\begin{lemma} Sind dir $R_j$ Ringe, so $S^\times = \prod_{j=1}^lR_j^\times$ \end{lemma}
\underline{Grund:} Muss sein $(a_1, ..., a_l)^{-1} = (a_1^{-1}, ..., a_l^{-1})$
Falls ein Isomorphismus $\psi: R \to S = \prod_{j=1}^lR_j$ vorliegt, so wird das Rechnen in $R$ zurückgeführt auf das gleichzeitig ("`\emph{parallele}"') Rechnen in dem $R_j$ wie folgt:\\ $\psi(a) = (a_1,...,a_l), \psi(b) = (b_1,...,b_l)$\\ $a \ast b = \psi^{-1}(\psi(a \ast b)) = \psi^{-1}(\psi(a) \ast \psi(b)) = \psi^{-1}((a_1 \ast b_1, ..., a_l \ast b_l))$
\underline{Praxis:} Berechne die $a_j \ast b_j$ gleichzeitig auf verschiedenen Prozessoren. Wende $\psi$, $\psi^{-1}$ wie oben an. Nützt nur, wenn $\psi$, $\psi^{-1}$ gut und schnell berechenbar sind.
\subsection{Der Chinesische Restsatz}
\underline{Frage:} Morgen ist Freitag, der 2. Juni. Nach wievielen ($x$ = ?) Tagen fällt frühestens der Dienstag auf einen 17. des Monats?
\underline{Vorraussetzung:} Chinesische Kalender vor ca. 2000 Jahren: Alle Monate haben 20 Tage.
\begin{tabular}{|r|c|c|c|c|c|c|c|c|c|c|}
\hline Wochentag & Fr & Sa & So & Mo & Di & Mi & Do & Fr & Sa & So \\ \hline Wochentagsnr. & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 0 & 1 & 2 \\ \hline Monatstagnr. & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline
\end{tabular} \\(Wochentagsnummer modulo 7, Monatstagnummer modulo 30)
Gesucht ist also die kleinste positive Lösung $x$ der Kongruenzen: \begin{alignat*}{2}
x &\equiv 4 &&\mod 7\\ x &\equiv 17-2 &&\mod 30
\end{alignat*}
$R$ sei euklidischer Ring, $a_1,\ldots,a_l, m_1,\ldots,m_l \in R$\\ \begin{equation}\label{eq:SystemSimultanerKongruenz (new)} x \equiv a_j \mod m_j,\ (j = 1, \ldots, l) \end{equation} heißt \emph{System simultaner Kongruenzen} (mit gesuchter Lösung $x \in R$).
\begin{bemerkung}
Im Allgemeinen gibt es \emph{keine} Lösung.\\
$x \equiv a \mod m \implies x \equiv a \mod m$, falls $d \mid m$\\
System: $x \equiv 1 \mod 4, x \equiv 0 \mod 6 \implies x \equiv 1 \mod 2, x \equiv 0 \mod 2 \implies 1 \equiv 0 \mod 2 \implies$ Widerspruch!
\end{bemerkung}
\begin{satz}[Chinesischer Restsatz, rechnerische Form]
Sei $R$ ein euklidischer Ring, $m_1, ..., m_l \in R$, $a_1,...,a_l \in R$ derartig, dass $\forall i,j \in \MdZ$ mit $1 \le i < j \le l$ gilt:\\
\[ \ggt(m_i, m_j) = 1\text{ ("`paarweise relativ prime $m_j$"')}\]
Dann hat das System simultaner Kongruenzen \eqref{eq:SystemSimultanerKongruenz} eine Lösung. Sämtliche Lösungen bilden \underline{eine} Restklasse modulo $m$ mit $m = m_1 \cdot \ldots \cdot m_l$
\end{satz}
\begin{beweis} \begin{description}
\item{$l=1$:} $x = a_1$ oder $x = (a_1 \mod m_1) \iff (x \equiv a_1) \mod m_1$ und $0 \le x \le m_1$
\item{$l=2$:} $x \equiv a_1 \mod m_1$. $x$ muss in der Form $x = a_1 + um_1, u \in R$ angesetzt
werden.\\
\emph{Idee}: Bestimme $u$ so, dass $x \equiv a_2 \mod m_2$. Also in $\overline R = R / m_2R$
soll werden:\\
$\overline a_1 + \overline u \overline m_1 = \overline{a_1 + um_1} = \overline a_2$, daher tut
es: $\overline u = (\overline a_2 - \overline a_1)\overline m_1^{-1}$\\
Geht, da $\overline m_1^{-1}$ existiert und da $\overline m_1 \in (R/m_2R)^\times$. Nach
dem Restklassensatz: $\overline m_1 \in (R/m_2R)^\times \iff \ggt(m_1,m_2) = 1$\\
Algorithmisch $\overline u = \overline m_1^{-1}$, $u$ kann mit LinKom-Satz, also
euklidischem Algorithmus, bestimmt werden. \emph{Erinnerung}: $\ggt(m_1,m_2) = um_1 + vm_2,\ u,v$
berechnet der Algorithmus.\\
$1 = \overline u \overline m_1, \overline m_2 = 0, \overline u = \overline m_1^{-1}$\\
Für dieses $u \in R$ ist $x = a_1 + um_1$ (eventuell $\mod m, m_2$) die gesuchte
Lösung.
\item{$l>2$:} Induktionshypothese löst $x' \equiv a_j \mod m_j (j = 1,..., l-1)$.\\
Löse dann $x \equiv x' \mod m_1 \cdot ... \cdot m_{l-1}$ ($\implies x \equiv x' \equiv a_j \mod m_j, j=1,...,l-1) \implies x \equiv a_l \mod m_l \implies$ $x$ ist die gesuchte Lösung.
\end{description} \end{beweis}
\begin{beispiel} Gegeben sind die Kongruenzen: \begin{alignat*}{2}
x &\equiv 4 &&\mod 7\\ x &\equiv 19 &&\mod 30
\end{alignat*} Ansatz: $x=4 + u\cdot 7 \equiv 19 \mod 30$. Im $\MdZ (new)/30\MdZ (new)$: $\overline 4 + \overline u\cdot \overline 7 = \overline {19} \folgt \overline u = (\overline {19} - \overline 4)^{-1} \cdot \overline 7^{\,-1}$. Es ist $\overline 7^{\,-1}=\overline {13}$, also $u \equiv 13\cdot 15$, etwa $x = 4 + 13 \cdot 15 \cdot 7 \equiv 109 \mod 210$.
Wir fügen eine Bedingung hinzu: $x\equiv 1 \mod 77$. So ist nun zu lösen: \begin{alignat*}{2}
x &\equiv 109 &&\mod 30\\ x &\equiv 1 &&\mod 11
\end{alignat*} Es ist $\overline {210}^{\,-1} = \overline 1$ im $\MdF (new)_{11}$, also $x=109+2\cdot 210 \equiv 529 \mod 11\cdot3\cdot 7$ \end{beispiel}
\begin{bemerkung}[zur Praxis] % Hilfe! wer das verstanden hat oder korrekt mitgeschrieben hat, bitte korrigieren und ggf. erklären. Das Sytem $x\equiv x_i \mod m_i$, $(i=0,\ldots,l)$. Der Beweis liefert eine $\gamma$-adische Darstellung von $x$ und $m=y$ $\gamma=(m_0,\ldots,m_l)$ wie folgt: $y = z_{l-1}M_{l-1}+\cdots+ z_0$. Die $z_i$ sind rekursiv aus $z_0 = x_0 \bmod m_0$, $y' \equiv x_i' \bmod m_j$, $(i=1,\ldots,l)$. Also $y'=\frac{x-z_0}{m_0}$, $x_i' = (x_i - z_0)u_{i0} \bmod m_j$. $\overline {u_{i0}} = \overline {m_0^{-1}}$ in $\MdZ (new)/m_i\MdZ (new)$. $x_i'$ in $\gamma'$-adischer Darstellung nach Induktions-Voraussetzung $(\gamma'=(m_1,\ldots,m_l))$.
Empfehlung zur Praxis, vor allem wenn viele Kongruenzen zu den selben $m_i$ zu lösen sind: \begin{enumerate} \item Berechne die $u_{ij}$ nur einmal. \item Belasse die Ergebnisse $m$ in der Form $x=(z_{l-1},\ldots,z_0)_\gamma$ \end{enumerate} \end{bemerkung}
Zum paralellen Rechnen: Seien $R,m_1,\ldots,m_l$ wie im chinesischen Restsatz. Betrachte die Abbildung \begin{align*} R/mR &\to \prod_{j=1}^l (R/m_jR) \\ \psi: x + mR &\mapsto (\ldots, x + m_jR, \ldots ) \end{align*} $\psi$ ist wohldefiniert: $x+mR = x'+mR \iff x \equiv x' \mod m \iff x \equiv x' \mod m_j$ und ein Ringhomomorphismus (leicht zu sehen).
Wir beobachten: Ist $\psi: A\to B$ eine Abbildung, so gilt, dass $\psi$ injektiv genau dann ist wenn die Gleichung $\psi(x) = b$ höchstens eine Lösung $x$ hat. Surjektivität heißt analog, dass jede Gleichung $\psi(x) = b$ mindestens eine Lösung $x$ hat. $\psi$ bijektiv ist dann gleichbedeutend damit, dass $\psi(x) =b $ genau eine Lösung hat.
Für obiges $\psi$ gilt: $b = (\ldots,a_j+ m_jR,\ldots)$. $\psi(x+m_jR)=b$: $(\ldots,x+m_jR,\ldots) =(\ldots,a_j+m_jR,\ldots) = b$. $x+mR$ Urbild von $b$ $\iff \forall j: x+m_jR_j = a_j+m_jR \iff \forall j: x \equiv a_j \mod m_j$. Also: \begin{itemize} \item $\psi$ surjektiv $\iff \forall b \exists \text{Lösung } x\equiv a_j \mod m_j$ \item $\psi$ injektiv $\iff$ Lösung $x$ ist eindeutig modulo $m$ \end{itemize} Ergebnis: Der chinesische Restsatz wie oben ist gleichbedeutend mit:
\begin{satz}[Theorem B, Chinesischer Restsatz, theoretische Form] $R$ ein euklidischer Ring, $m_1,\ldots,m_l\in R$, $\ggt(m_i,m_j)=1$ für $i\ne j$. Dann hat man den Ringisomorphismus: \begin{align*} R/mR &\to \prod_{j=1}^l (R/m_jR) \\ \psi: x + mR &\mapsto (\ldots, x + m_jR, \ldots ) \end{align*} \end{satz}
\begin{bemerkung}[Zur Praxis] $\psi^{-1}$ wird gegeben durch lösen simultaner Kongruenzen. "`Komponentenweises Rechnen: Rechnen im $R/mR$ ersetzt durch paralleles Rechnen in den $R/m_jR$"' \end{bemerkung}
\begin{bemerkung}[Theoretische Anwendung] Voraussetzungen wie im Satz. Die Einheitengruppe $(R/mR)^\times$ ist isomorph durch $\psi$ zu $\prod_{j=1}^l (R/m_jR)^\times $. Ist $R=\MdZ (new)$, so gilt $\varphi(m) = \prod_{j=1}^l \varphi(m_j)$, also ein neuer Beweis für die Multiplikativität von $\varphi$. \end{bemerkung}
\section{Ausgewählte Anwendungen von Kongruenzen}
\subsection{Diophantische Gleichungen} Sei $0\ne f \in \MdZ (new)[X_1,\ldots,X_n]$ (Polynom mit $n$ Unbekannten und Koeffizienten aus $\MdZ (new)$), $x=(x_1,\ldots,x_n)\in\MdZ (new)^n$.
Eine diophantische Gleichung ist eine Gleichung der Form $f(x)=0$, $f$ wie oben, mit eine "`Lösung $x$"'.
Der Wunsch hier ist: Man finde möglichst viel Informationen über die Menge $\mathcal{V}_f(\MdZ (new)) := \{ x\in\MdN (new)^n \mid f(x) = 0\}$ aller ganzzahligen Lösungen.
Das Problem ist oft extrem schwierig. Zum Beispiel die diophantischen Gleichungen $x^n+y^n+z^n=0$, $x=(x,y,z)$, auch bekannt als das Fermatproblem.
Information für Logik-Freunde: Das 10. Hilbertsche Problem (Paris 1900): \begin{quote} Man finde einen Algorithmus, der zu gegebenem $f\in \MdZ (new)[X1,\ldots,X_n]$ entscheidet, ob $\mathcal{V}_f(\MdZ (new)) = \emptyset$ oder $\mathcal{V}_f(\MdZ (new)) \ne \emptyset$ ist. \end{quote} Satz von Julia Robison (1910-85), J. Matjasevi\v{c}: Es gibt keinen solchen Algorithmus!
Triviale, aber wichtige Methode: $f(x)=0$ hat Lösung $x\in\MdZ (new)^n$ $\folgt$ $f(x)=0$ hat Lösung $x \in \MdR (new)^n$ (Analysis) und $\forall m \in \MdZ (new): f(x) \equiv 0 \mod m$ lösbar $\iff \forall t \in \MdNp (new) \forall p\in\MdP (new): f(x) \equiv 0 \mod p^t$ lösbar. Die Folgerung ist, dass falls für ein $m\in\MdNp (new)$ gilt, dass für alle $(x_1,\ldots,x_n)\in\MdZ (new)^n$, $0\le x_j < m_j$ gilt: $f(x)\not\equiv 0 \mod m$, so gilt $\mathcal{V}_j(\MdZ (new))= \emptyset$, es gibt also keine Lösung.
\begin{beispiel} $f=X_1^2 + X_2^2 - k$, $k\in\MdZ (new)$, diophanischsche Gleichung $x_1^2 + x_2^2 = k$. Unlösbar für $k<0$ (da keine Lösung in $\MdR (new)^2$). Nur interessant: $k>0$.
Betrachtung modulo 4:\\ $0^2 = 0, (\pm1)^2 = 1, (\pm2)^2= 0 \folgt (x_1^2 + x_2^2) \bmod 4 = \begin{cases} 0+0 \\ 0+1 \\ 1+1 \end{cases} \in \{0,1,2\}$.
Für $k\equiv 3 \mod 4$ hat $x_1^2 + x_2^2 = k$ also keine ganzzahlige Lösung!
Es kann eine Primzahl $p\ne 2$ nur dann Summe zweier Quadrate sein, wenn $p\equiv 1 \mod 4$ ist. Hier gilt auch die Umkehrung, Beweis folgt eventuell später. \end{beispiel}
\begin{beispiel} $f=X_1^2 + X_2^2 + X_3^2 - k$, also $x^2 + y^2 + z^2 = k$. Modulo 4 führt hier zu keiner Aussage. Wie betrachten modulo 8: $0^2 = 0$, $(\pm1)^2 = 1$, $(\pm2)^2 = 4$, $(\pm3)^2=1$, $(\pm4)^2 = 0$. Also gilt: $(x_1^2 + x_2^2 + x_3^2) \bmod 8 = \begin{cases} 0+0+0 \\ 0+1+0 \\ 1+1+1 \\ 1+1+1 \\ 0 + 4+ 0 \\ \ \ \ \ \ \,\vdots % Spacing-Hack \end{cases} \in \{0,1,2,3,4,5,6\}$.
Ergebnis: Für $k<0$ oder $k\equiv 7 \mod 8$ hat die Diophantische Gleichung $x_1^2 + x_2^2 + x_3^2 = k$ keine Lösung.
Zur Information, nach Gauß: Die Umkehrung gilt auch für ungerade $k$. % Hä?
Satz von Lagrange: $x_1^2 + x_2^2 + x_3^2 + x_4^2 = k$ ($k\in\MdN (new)$) hat immer Lösungen. \end{beispiel}
Gelegentlich erlangt man Ergebnisse auch über andere Gleichungen:
\begin{beispiel} Gesucht sind Lösungen von $9^x + x^3 = k$ mit $x\in\MdNp (new)$.
Betrachtung modulo 9: $9^x \equiv 0 \mod 9$. $0^3 = 0$, $(\pm1)^3 = \pm1$, $(\pm2)^3 = \mp 1$, $(\pm3)^3 = 0$, $(\pm4)^3 = \pm1 \folgt x^x+ x^3 \equiv 0 , \pm 1 \mod 9$. Ergebnis: Für $k \equiv 2,3,4,5,6,7 \mod 9$ hat die Gleichung keine Lösung in $x\in\MdZ (new)$. \end{beispiel}
\subsection{Interpolation}
Hier sei $R=KX (new) \ni f$, $\alpha,\beta \in K$: \begin{align*} f(\alpha) = \beta &\iff (f-\beta)(\alpha) = 0 \\ &\iff (X-\alpha)\mid f-\beta \\ &\iff f \equiv \beta \mod (X-\alpha) \end{align*} Das Sytem $f \equiv \beta_j \mod (X-\alpha_j)$ $(j=0,\ldots,n) \iff \forall j=0,\ldots,n : f(\alpha_j)=\beta_j$ (Vorraussetzung $\alpha_i\ne \alpha_j$ für $i\ne j$, d.h $\ggt(X-\alpha_i,X-\alpha_j)\ne 0$).
Der Chinesische Restsatz ergib nun: Zu gegebenen $n+1$ Punkten $\alpha_0, \ldots, \alpha_n \in K$ ($\alpha_i \ne \alpha_j$) und Punkten $\beta_0, \ldots, \beta_n\in K$ gibt es genau ein $f \bmod (X-\alpha_0)\cdots(X-\alpha_n)$, also $\ord(f) \le n$ mit $f(\alpha_j) = \beta_j$. Damit ist das Interpolationsproblem gelöst.
%Vorlesung 08.06.2006
\emph{Frage:} Kann man bei Interpolation die Tangentensteigung (allgemein $f^{(j)}(\alpha_k)$) auch vorschreiben (Hermitesche Interpolationsaufgabe)? Ja für $K=\MdQ (new), \MdR (new), \MdC (new)$ (Übung).
$f\in KX (new)$, $(X-\alpha)$-adische Darstellung. Ziffern $z_j \in KX (new)$ haben Grad $z:j < \grad (X-\alpha)=1$, das heißt $z_j \in K$. $f=\sum_{j=0}^n z_j (X-\alpha)^j$, das ist die Taylor-Entwicklung in $\alpha$. $z_j$ gegeben durch $\frac{f^{(j)}(\alpha)}{j!}$. \begin{equation}\label{eq:3.5stern}
f \equiv g_{\alpha,d} \mod (X-\alpha)^{\alpha+1}, \qquad
g_{\alpha,d}:=\sum_{j=0}^d z_j(X-\alpha^j)
\end{equation} $g_{\alpha,d}$ ist gegeben durch $f(\alpha),f'(\alpha),\dotsc,f^{(d)}(\alpha)$.\\System \eqref{eq:3.5stern} entspricht der Vorgabe der $f^{(j)}(\alpha)$, Interpolation mit $m_{j,k}=(X-\alpha_k)^{d_j}$ ist lösbar mit dem Restsatz.
\subsection{Rechnen im Computer mit großen ganzen Zahlen}
Prinzip: Gleicheit in \MdZ (new)\ entspricht Kongruenz und einer passender Abschätzung. \begin{bemerkung}
$m\in\MdN,\ m>1$, etwa $2 \nmid m$. Ist $u \equiv v \mod m$ und
$|u|,|v|\leq \frac{m}{2}$, so ist $u=v$, weil $u,v$ sind im
symmetrischen $\text{Versys}_m$.
\end{bemerkung} Wende dies an auf die Berechnung von $f(x), f\in \MdZ (new)[X_1,\dotsc,X_n],\ x=(x_1,x_2,\dotsc,x_n) \in \MdZ (new)^n$. Kennt man eine Schranke $|f(x)|<\frac{m}{2}$, so genügt es, $f(x) \mod m$ auszurechnen. $f(x) \mod m$ kann für $m=m_1 \cdot \dotsb \cdot m_l$ durch Berechnen von $y_j=f(x) \mod m_j\ (j=1,\dotsc,l)$ ersetzt werden, das ergibt simultane Kongruenz $y=y_j \mod m_j$, die mit dem chinesischen Restsatz gelöst werden kann.
\section{Struktur der Primrestklassengruppe mod $m$} $R$ euklidisch, $m=\prod_{i=1}^l p_i^{t_i}$ Primzerlegung, $t_j \in \MdN (new)_+$. Aus dem Chinesischen Restsatz: $(R/mR)^{\times} \cong \prod_{j=1}^l (R/p_j^{t_j} R)$ (beachte: $\ggt(p_i^{t_i},p_j^{t_j})=1$ für $i \neq j$). Es genügt also $G:=R/p^t R$ mit $p\in P,\ t\in \MdN (new)_+$ zu betrachten. Hier nur der Fall $R=\MdZ (new)$ $(R=\MdF (new)_p[X ]$ geht ähnlich).
\emph{Erinnerung:} $t=1,\ \MdZ (new)/p\MdZ (new)=\MdF (new)_p,\ \MdF (new)_p^{\times}$ ist zyklich, es existiert eine Primitivwurzel $w \mod p$.
\emph{Frage:} Wie ist der Fall für $t>1$?
Für $p>2$ existiert eine Primitivwurzel!
Gesucht ist also eine Primitivwurzel $u$, das heißt $\ord \overline u = \varphi\left(p^t\right)=(p-1)p^{t-1}$ in $G$. Es genügt $u_1,u_2 \in \MdZ (new)$ mit $p-1 \mid \ord \overline u_1$ und $p^{t-1} \mid \ord \overline u_2$ zu finden. Wegen $\ord \overline u_j \mid \#G=(p-1)p^{t-1}$ gilt $s \mid p-1$. Daraus folgt, für $v_1:=u_1^{p^{t-1}},v_1:=u_2^{p-1}$ ist \[ \ord \overline v_1=\ord \overline u_1^{p^{t-1}}=\frac{\ord \overline u_1}{\ggt\left(\ord \overline u_1,p^{t-1} \right)}=\frac{(p-1)p^r}{p^r}=p-1. \] Ebenso: $\ord\overline v_2=p^{t-1}$ (Nachrechnen). Aus Übungsaufgabe 3 (a) Blatt 7 folgt mit $u:=v_1v_2 \mod p^t,\ \ord \overline u=(p-1)p^{t-1}$. Bevor wir fortfahren, benötigen wir noch ein Lemma, das wir zum Beweis eines Hilfssatzes benötigen.
\begin{lemma}[$(1+p)$--Lemma]\label{lemma:1+p}
$p\in\MdP,\ p>2,\ r\in \MdN_+,\ u\in \MdZ.$ Dann gilt:
$(1+up)^{p^{r-1}} \equiv 1+up^r \mod p^{r+1}$.
\end{lemma} \begin{beweis}
Beweis via Induktion nach $r$.
\begin{description}
\item{$r=1$:} $(1+up)^{p^{1-1}}=1+up\equiv1+up^1 \mod p^2\quad
\checkmark$.\\
\item{$r>1$:} Induktionshypothese (für $r-1$):
\[
(1+up)^{p^{r-2}}\equiv 1+ up^{r-1} \mod p^r.
\]
$\implies(1+up)^{p^{r-2}}=1+up^{r-1}+zp^r$ mit $z\in\MdZ$
$\implies
(1+up)^{p^{r-1}}=\left((1+up)^{p^{r-2}}\right)p=\left(1+\left(up^{r-1}+zp^r\right)\right)^p=1+\sum_{i=1}^p
\underbrace{{p \choose i}}_{\in \MdZ}
\underbrace{\left(up^{r-1}+zp^r\right)}^i_{=\left(p^{r-1}(u+zp)\right)^i=:c_i}$.\\
\item{$r\geq 2,\ i>2$:} $v_p(c_i)=\underbrace{v_p\left({p \choose
i}\right)}_{\geq 0} +
v_p\left(p^{(r-1)i}\right)+\underbrace{v_p(u+zp)^i}_{\geq 0}
\geq (r-1)i \geq (r-1)r>r+1 \implies p^{r+1} \mid c_1 \implies
c_i \equiv 0 \mod p^{r+1}$.
\item{$i=2$:} $v_p(c_2)=\underbrace{v_p\left( \frac{p(p-1)}{2} \right)}_{\geq
1} + \underbrace{v_p\left( p^{2(r-1)} \right)}_{=2(r-1)} + \underbrace{v_p(u+zp)^2}_{\geq
0} \geq 2r-2+1=2r-1 \geq r+1 \implies c_2 \equiv 0 \mod p^{r+1}$.
\item{$i=1$:} $c_1=p\cdot p^{r-1}(u+zp)=up^r+zp^{r+1}\equiv up^r \mod
p^{r+1}$.
\end{description}
$\implies$ Behauptung.
\end{beweis} \begin{hilfssatz}
Sei $p\in\MdP,\ p>2,\ t\in \MdN_+$.
\begin{enumerate}
\item Ist $w$ eine Primitivwurzel $\mod p$, so gilt in $G=\left(\MdZ/p^t
\MdZ\right)^{\times}:\ p-1 \mid \ord \overline w,\ \overline
w=w+p^t \MdZ$. (\emph{$u_1=w$ wählbar}).
\item $\ord (\overline{1+p})=p^{t-1}$ (\emph{$v_2=1+p$
wählbar}).
\end{enumerate}
\end{hilfssatz} \begin{beweis} \begin{enumerate}
\item Sei $l=\ord \overline w$, also $\overline w^l=1$, das
heißt $w^l\equiv 1 \mod p^t$. $t\geq 1 \implies w^l \equiv 1
\mod p^1 \implies $ in $\MdF_p$ ist $\overline w^l=1$, $\ord
\overline w=p-1 \implies p\cdot a \mid l$ (Elementar-Ordnungssatz).
\item Folgt aus Lemma \ref{lemma:1+p}
\end{enumerate}
$(1+p)^{p^{t-1}}\equiv1+1\cdot p^t \mod p^{t-1} \implies (1+p)^{p^{t-1}}\equiv 1 \mod p^t \implies \overline{1+p}^{p^{t-1}} \implies \ord \overline{1+p} \mid p^{t-1}$. Für $t \geq 2$ ist noch zu zeigen: $(1+p)^{p^{t-2}} \neq 1$. $(1+p)^{p^{t-2}} \equiv 1+ p^{t-1} \mod p^t$ (nach Lemma \ref{lemma:1+p}). $\overline{1+p}^{p^{t-2}}=\overline 1 + \underbrace{\overline{p^{t-1}}}_{\neq 0} \neq \overline 1 =1$. \end{beweis}
Gezeigt (für $p>2$): \begin{satz}[Struktursatz für $(\MdZ (new)/p^t \MdZ (new))^{\times}$, eigentlich ein Theorem] Sei $p\in\MdP (new),\ t\in \MdN (new)_+$. Dann gilt: \begin{enumerate}
\item Falls $p>2$, so ist $(\MdZ/p^t \MdZ)^{\times}$ zyklisch
(das heißt, es gibt eine Primitivwurzel $u \mod p^t$, also $(\MdZ/p^t
\MdZ)^{\times}=\{ 1,\overline u,\dotsc, \overline
u^{p^{t-1}(p-1)-1}\}$
\item Falls $p=2$: $(\MdZ/2 \MdZ)^{\times},\ (\MdZ/4
\MdZ)^{\times}$ zyklisch. Für $t>2$ ist $(\MdZ/2^t
\MdZ)^{\times}$ \emph{nicht} zyklisch, doch es gilt: Jedes
$\overline a \in (\MdZ/2^t \MdZ)^{\times}$ lässt sich eindeutig
in der Form $\overline a=\overline{(-1)}^{\ep} \cdot \overline 5
^s$ schreiben, mit $\ep \in \{0,1\}, s \mod 2^{t-2}$
(eindeutig). $(\MdZ/2^t \MdZ)^{\times}$ ist sozusagen bis auf
das Vorzeichen $(-1)^{\ep}$ zyklisch.
\end{enumerate} \end{satz}
\underline{Aufgabe:} \\ Berechne mit dem Computer det $A$ (exakt), $A \in \MdZ (new)^{n \times n}$ \\ Soll sein $n$ mäßig groß, $A=(a_{ij})$, die $a_{ij}$ mäßig groß.\\ Naives Verfahren: Gauß-Algorithmus in $\MdQ (new)$: \\ Ärger: Sehr große Integer-Zahlen als Zähler und Nenner entstehen während der Rechnung unkontrolliert. Mögliche bessere Vorgehensweise, etwa $|a_{ij}| \leq s$ (Schranke) \\ Leibnitzformel: det $A=\sum_{\pi \in S_n}\mbox{sgn}(\pi)\prod_{i=1}^na_{i,\pi(i)}$ liefert Abschätzung $|\mbox{det }A|\leq s^n\cdot n!$ ($n! = #S_n$)\\ Schranke $S = 2\cdot|\mbox{det }A| = s^n\cdot n!$ kann sehr groß sein. Wähle Primzahlen ($\neq 2$) $p_1,...,p_t$ ($t$ verschieden) mit $S \leq p_1\cdot ... \cdot p_t$. Dann $|\mbox{det }A| \leq \frac{p_1\cdot ... \cdot p_t}{2} = \frac{m}{2}\mbox{, }m=p_1\cdot ... \cdot p_t$\\ Kann oft sein: $t$ mäßig groß, alle $p_j$ mäßig groß. (z. B.: $s=100$, $n=100 \Rightarrow S = 100^{100}\cdot 2 \cdot 100! \leq 2 \cdot 100^{120}$ Es reichen also 130 $p_j$'s mit $p_j > 100$, diese können $< 1000$ gewählt werden $\Rightarrow$ in $\MdF (new)_{p_j}$ kann sehr gut und schnell gerechnet werden!\\ $\Rightarrow$ Berechnung von det $\overline{A}$, $\overline{A} = (\overline{a_{ij}})$ in $\MdF (new)_p^{n \times n}$ kann durch Herstellen von Dreiecksform von $\overline{A}$ für mäßig große $n$ schnell berechnet werden. (Durch Arbeiten in Versys$_p$ entstehen niemals große Zahlen!) Das ergibt $y_j \in \mbox{Versys}_p$ mit det $A$ mods $p_j = y_j$. Es ist dann $y \equiv y_j$ mod $p_j$ zu lösen (simultane Kongruenz $m=p_1\cdot ... \cdot p_t$). Daher für $y \in$ Versys$_m$ (symm.) ist det $A=m$. $y$ kann sehr groß sein, aber die Kongruenz ergibt sehr große Zahlen nur kontrolliert! (Mäßig große Zahlen, falls man mit $\gamma$-adischer Darstellung von $y=$det $A$, $\gamma=(p_1,...,p_t,...)$ zufrieden ist.
\end{document}