Kurs:Zahlentheorie (Osnabrück 2008)/Vorlesung 4/latex
\setcounter{section}{4}
\zwischenueberschrift{ Die Restklassenringe $\Z/(n)$ }
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Anillo_ciclico.png} }
\end{center}
\bildtext {} }
\bildlizenz { Anillo cíclico.png } {Romero Schmidtke} {FrancoGG} {es.wikipedia.org} {CC-by-sa 3.0} {}
\inputfaktbeweis
{Restklassenring (Z)/Einheit/Charakterisierung/Teilerfremd/Fakt}
{Satz}
{}
{
Genau dann ist
\mavergleichskette
{\vergleichskette
{ a
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {Einheit}{}{}
modulo $n$
\zusatzklammer {d.h. $a$ repräsentiert eine Einheit in \mathlk{\Z/(n)}{}} {} {,}
wenn
\mathkor {} {a} {und} {n} {}
\definitionsverweis {teilerfremd}{}{}
sind.
}
{
Sind \mathkor {} {a} {und} {n} {}
\definitionsverweis {teilerfremd}{}{,}
so gibt es nach
Fakt *****
eine Darstellung der $1$, es gibt also ganze Zahlen
\mathl{r,s}{} mit
\mavergleichskettedisp
{\vergleichskette
{ra+sn
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Betrachtet man diese Gleichung modulo $n$, so ergibt sich
\mavergleichskette
{\vergleichskette
{ra
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in
\mathl{\Z/(n)}{.} Damit ist $a$ eine Einheit mit Inversem
\mavergleichskette
{\vergleichskette
{ a^{-1}
}
{ = }{ r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Ist umgekehrt $a$ eine Einheit in
\mathl{\Z/(n)}{,} so gibt es ein
\mathl{r \in \Z/(n)}{} mit
\mathl{ar=1}{} in
\mathl{\Z/(n)}{.} Das bedeutet aber, dass
\mathl{ar-1}{} ein Vielfaches von $n$ ist, so dass also
\mavergleichskettedisp
{\vergleichskette
{ ar-1
}
{ =} { sn
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt. Dann ist aber wieder
\mavergleichskette
{\vergleichskette
{ar-sn
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und $a$ und $n$ sind teilerfremd.
\inputfaktbeweis
{Restklassenringe von Z/Charakterisierung Körper/Prim/Fakt}
{Korollar}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Der
\definitionsverweis {Restklassenring}{}{}
\mathl{\Z/(n)}{} ist genau dann ein
\definitionsverweis {Körper}{}{,}}
\faktfolgerung {wenn $n$ eine
\definitionsverweis {Primzahl}{}{}
ist.}
\faktzusatz {}
\faktzusatz {}
}
{
Die Zahl $n\geq 2$ ist genau dann prim, wenn sie teilerfremd zu jeder Zahl $a$,
\mathl{0< a < n}{,} ist. Dies ist nach
Satz 4.1
genau dann der Fall, wenn in
\mathl{\Z/(n)}{} jedes von $0$ verschiedene Element eine Einheit ist.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Leonhard-Euler_by_Handmann_.png} }
\end{center}
\bildtext {Leonhard Euler (1707-1783)} }
\bildlizenz { Leonhard Euler by Handmann .png } {Emanuel Handmann} {QWerk} {Commons} {PD} {http://www.euler-2007.ch/doc/Bild0015.pdf}
\inputdefinition
{}
{
Zu einer natürlichen Zahl $n$ bezeichnet
\mathl{{\varphi (n)}}{} die Anzahl der Elemente von
\mathl{(\Z/(n))^{\times}}{.} Man nennt
\mathl{{\varphi (n)}}{} die \definitionswort {Eulersche Funktion}{.}
}
\inputbemerkung
{}
{
Die
\definitionsverweis {Eulersche Funktion}{}{}
\mathl{\varphi(n)}{} gibt also für
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nach
Satz 4.1
an, wie viele Zahlen $r$,
\mathl{0 \leq r<n}{,} zu $n$
\definitionsverweis {teilerfremd}{}{}
sind.
}
\inputfaktbeweis
{Restklassenringe von Z/Einheiten/Euler/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei $n$ eine natürliche Zahl.}
\faktfolgerung {Dann gilt für jede zu $n$ teilerfremde Zahl $a$ die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ a^{\varphi (n)}
}
{ =} { 1 \!\! \! \mod n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Das Element $a$ gehört zur Einheitengruppe
\mathl{{ \left( \Z/(n) \right) }^{\times}}{,} die
\mathl{\varphi(n)}{} Elemente besitzt. Nach
dem Satz von Lagrange
ist aber die Gruppenordnung ein Vielfaches der Ordnung des Elementes.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Joseph-Louis-Lagrange.jpeg} }
\end{center}
\bildtext {Joseph-Louis Lagrange (1736 Turin - 1813 Paris)} }
\bildlizenz { Joseph-Louis Lagrange.jpeg } {unbekannt} {Katpatuka} {Commons} {PD} {http://de.wikipedia.org/wiki/Bild:Joseph-Louis_Lagrange.jpeg}
Als Spezialfall erhalten wir den sogenannten kleinen Fermatschen Satz:
\inputfaktbeweis
{Zahlentheorie/Primzahlen/Kleiner Fermat/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Für eine
\definitionsverweis {Primzahl}{}{}
$p$ und eine beliebige ganze Zahl $a$ gilt}
\faktfolgerung {
\mathdisp {a^p\equiv a\mod p} { . }
}
\faktzusatz {Anders ausgedrückt:
\mathl{a^p-a}{} ist durch $p$ teilbar.}
\faktzusatz {}
}
{
Ist $a$ nicht durch $p$ teilbar, so definiert $a$ ein Element $\bar a$ in der
\definitionsverweis {Einheitengruppe}{}{}
\mathl{{ \left( \Z/(p) \right) }^{\times}}{;} diese Gruppe hat die
\definitionsverweis {Ordnung}{}{}
\mathl{{\varphi (p)}=p-1}{,} und nach
dem Satz von Lagrange
gilt
\mavergleichskette
{\vergleichskette
{ {\bar a}^{p-1}
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Durch Multiplikation mit $a$ ergibt sich die Behauptung. Für Vielfache von $p$ gilt die Aussage ebenso, da dann beidseitig $0$ steht.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Pierre_de_Fermat.jpg} }
\end{center}
\bildtext {Pierre de Fermat (1607/08-1665)} }
\bildlizenz { Pierre de Fermat.jpg } {} {Magnus Manske} {en.wikipedia.org} {PD} {http://www-groups.dcs.st-and.ac.uk/~history/PictDisplay/Fermat.html}
\inputbeispiel{}
{
Es sei beispielsweise
\mavergleichskette
{\vergleichskette
{p
}
{ = }{5
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist für
\mathdisp {a=1 \, \, : \, 1^5 = 1 \mod 5} { }
\mathdisp {a=2 \, \, : \, 2^5 = 32 = 2 \mod 5} { }
\mathdisp {a=3 \, \, : \, 3^5 = 243 = 3 \mod 5} { }
\mathdisp {a=4 \, \, : \, 4^5 = 1024 = 4 \mod 5} { . }
}
\inputdefinition
{}
{
Ein \definitionsverweis {Körper}{}{} heißt \definitionswort {endlich}{,} wenn er nur endlich viele Elemente besitzt.
}
\inputfaktbeweis
{Endliche Körper/Produkt aller Einheiten/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $K$ ein
\definitionsverweis {endlicher Körper}{}{.}}
\faktfolgerung {Dann ist das Produkt aller von $0$ verschiedener Elemente aus $K$ gleich $-1$.}
\faktzusatz {}
\faktzusatz {}
}
{
Die Gleichung
\mavergleichskette
{\vergleichskette
{x^2
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
hat in einem Körper nur die Lösungen $1$ und $-1$, die allerdings gleich sein können. Das bedeutet, dass für
\mavergleichskette
{\vergleichskette
{x
}
{ \neq }{1, -1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
immer
\mavergleichskette
{\vergleichskette
{x
}
{ \neq }{x^{-1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Damit kann man das Produkt aller Einheiten als
\mathdisp {1 (-1) x_1 x_1^{-1} \cdots x_k x_k^{-1}} { }
schreiben. Ist
\mavergleichskette
{\vergleichskette
{-1
}
{ \neq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so ist das Produkt $-1$. Ist hingegen
\mavergleichskette
{\vergleichskette
{-1
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so fehlt in dem Produkt der zweite Faktor und das Produkt ist
\mavergleichskette
{\vergleichskette
{1
}
{ = }{-1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\inputfaktbeweis
{Restklassenkörper von Z/Wilson/Fakt}
{Korollar}
{}
{
\faktsituation {Es sei $p$ eine
\definitionsverweis {Primzahl}{}{.}}
\faktfolgerung {Dann ist
\mavergleichskette
{\vergleichskette
{ (p-1)!
}
{ = }{-1 \!\!\! \mod p
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Dies folgt unmittelbar aus
Satz 4.9,
da ja die Fakultät durch alle Zahlen zwischen
\mathkor {} {1} {und} {p-1} {}
läuft, also durch alle
\definitionsverweis {Einheiten}{}{}
im
\definitionsverweis {Restklassenkörper}{}{}
\mathl{\Z/(p)}{.}
Wir wollen im folgenden die Struktur der Restklassenringe
\mathl{\Z/(n)}{} verstehen, insbesondere, wenn die Primfaktorzerlegung von $n$ bekannt ist.
\inputfaktbeweis
{Restklassenringe (Z)/Teiler und Morphismus/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Seien
\mathkor {} {n} {und} {k} {}
positive natürliche Zahlen, und $k$ teile $n$.}
\faktfolgerung {Dann gibt es einen kanonischen
\definitionsverweis {Ringhomomorphismus}{}{}
\maabbeledisp {} {\Z/(n)} { \Z/(k)
} { (a \mod n) } { (a \mod k)
} {.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir betrachten die Ringhomomorphismen
\mathdisp {\begin{matrix} \Z & \stackrel{\varphi}{\longrightarrow} & \Z/(k) \\ \!\phi \!\downarrow & & \\ \Z/(n) & & \end{matrix}} { }
Aufgrund der Teilerbeziehung haben wir die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{kern} \phi
}
{ =} {(n)
}
{ \subseteq} { (k)
}
{ =} { \operatorname{kern} \varphi
}
{ } {
}
}
{}{}{.}
Aufgrund des
Homomorphiesatzes
hat man daher einen kanonischen Ringhomomorphismus von links unten nach rechts oben.
Zur Formulierung des Chinesischen Restsatzes erinnern wir an den Begriff des Produktringes.
\inputdefinition
{}
{
Es seien
\mathl{R_1 , \ldots , R_n}{}
\definitionsverweis {kommutative Ringe}{}{.}
Dann heißt das Produkt
\mathdisp {R_1 \times \cdots \times R_n} { , }
versehen mit komponentenweiser Addition und Multiplikation, der \definitionswort {Produkt\-ring}{} der
\mathbed {R_i} {}
{i=1 , \ldots , n} {}
{} {} {} {.}
}
\inputfaktbeweis
{Restklassenringe (Z)/Chinesischer Restsatz/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $n$ eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} { p_1^{r_1} \cdot p_2^{r_2} { \cdots } p_k^{r_k}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {die $p_i$ seien also verschieden und
\mavergleichskettek
{\vergleichskettek
{ r_i
}
{ \geq }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {.}}
\faktfolgerung {Dann induzieren die kanonischen Ringhomomorphismen
\maabb {} {\Z/(n)} {\Z/(p_i^{r_i} )
} {}
einen
\definitionsverweis {Ringisomorphismus}{}{}
\mavergleichskettedisp
{\vergleichskette
{ \Z/(n)
}
{ \cong} { \Z/(p_1^{r_1} ) \times \Z/(p_2^{r_2} ) \times \cdots \times \Z/(p_k^{r_k} )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {Zu gegebenen ganzen Zahlen
\mathl{(a_1,a_2 , \ldots , a_k)}{} gibt es also genau eine natürliche Zahl
\mavergleichskette
{\vergleichskette
{a
}
{ < }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die die
\betonung{simultanen Kongruenzen}{}
\mathdisp {a= a_1 \mod p_1^{r_1}, \,\, a= a_2 \mod p_2^{r_2}, \, \ldots , \,\, a= a_k \mod p_k^{r_k}} { }
löst.}
\faktzusatz {}
}
{
Da die Ringe links und rechts beide endlich sind und die gleiche Anzahl von Elementen haben, nämlich $n$, genügt es, die Injektivität zu zeigen. Es sei $x$ eine natürliche Zahl, die im Produktring
\zusatzklammer {rechts} {} {}
zu $0$ wird, also modulo $p_i^{r_i}$ den Rest $0$ hat für alle
\mathl{i=1,2 , \ldots , k}{.} Dann ist $x$ ein Vielfaches von $p_i^{r_i}$ für alle
\mathl{i=1,2 , \ldots , k}{,} d.h. in der Primfaktorzerlegung von $x$ muss $p_i$ zumindest mit den Exponenten $r_i$ vorkommen. Also muss $x$
nach Satz 3.10
ein Vielfaches des Produktes sein, also ein Vielfaches von $n$. Damit ist
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in
\mathl{\Z/(n)}{} und die Abbildung ist injektiv.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Tablero_producto_anillos_cíclicos_2.png} }
\end{center}
\bildtext {} }
\bildlizenz { Tablero producto anillos cíclicos 2.png } {Romero Schmidtke} {FrancoGG} {es.wikipedia.org} {CC-by-sa 3.0} {}
\inputaufgabeloesungvar{
(a) Bestimme für die Zahlen $3$, $5$ und $7$ modulare Basislösungen, finde also die kleinsten positiven Zahlen, die in
\mathdisp {\Z/(3) \times \Z/(5) \times \Z/(7)} { }
die Restetupel
$(1,0,0),\, (0,1,0)$ und $(0,0,1)$
repräsentieren.
(b) Finde mit den Basislösungen die kleinste positive Lösung $x$ der simultanen Kongruenzen
\mathdisp {x = 2 \!\! \mod 3 , \, \, \, \, x = 4 \!\! \mod 5 \text{ und } x = 3 \!\! \mod 7} { . }
} {
(a) $(1,0,0)$
- Alle Vielfachen von
\mathl{5 \cdot 7=35}{} haben modulo $5$ und modulo $7$ den Rest $0$. Unter diesen Vielfachen muss also die Lösung liegen. $35$ hat modulo $3$ den Rest $2$, somit hat $70$ modulo $3$ den Rest $1$. Also repräsentiert $70$ das Restetupel
\mathl{(1,0,0)}{.}
\mathl{(0,1,0)}{:} Hier betrachtet man die Vielfachen von $21$, und $21$ hat modulo $5$ den Rest $1$. Also repräsentiert $21$ das Restetupel
\mathl{(0,1,0)}{.}
\mathl{(0,0,1)}{:} Hier betrachtet man die Vielfachen von $15$, und $15$ hat modulo $7$ den Rest $1$. Also repräsentiert $15$ das Restetupel
\mathl{(0,0,1)}{.}
(b) Man schreibt
\zusatzklammer {in \mathlk{\Z/(3) \times \Z/(5) \times \Z/(7)}{}} {} {}
\mavergleichskettedisp
{\vergleichskette
{ (2,4,3)
}
{ =} {2(1,0,0)+4(0,1,0)+3(0,0,1)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Lösung ist dann
\mavergleichskettedisp
{\vergleichskette
{ 2 \cdot 70 +4 \cdot 21 +3 \cdot 15
}
{ =} { 140+84+45
}
{ =} {269
}
{ } {
}
{ } {
}
}
{}{}{.}
Die minimale Lösung ist dann
\mavergleichskette
{\vergleichskette
{ 269- 2 \cdot 105
}
{ = }{ 59
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
\zwischenueberschrift{Die Einheiten im Restklassenring}
Wir wollen zeigen, dass die Einheitengruppe
\mathl{({\mathbb Z}/(p))^\times}{,} wenn $p$ eine Primzahl ist, eine
\definitionsverweis {zyklische Gruppe}{}{}
ist, also von einem Element erzeugt wird. Der Restklassenring
\mathl{{\mathbb Z}/(p)}{} ist ein Körper, und wir werden hier nach einigen Vorbereitungen allgemeiner zeigen, dass jede endliche Untergruppe der multiplikativen Gruppe eines Körpers zyklisch ist. Dazu benötigen wir einige Resultate über kommutative Gruppen und zu Polynomringen über Körpern. Wir beginnen mit zwei gruppentheoretischen Lemmata. Wir verwenden multiplikative Schreibweise.
\inputfaktbeweis
{Gruppentheorie/Elementordnung vom Produkt/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $G$ eine
\definitionsverweis {kommutative Gruppe}{}{}
und
\mathl{x, y \in G}{} Elemente der
\definitionsverweis {endlichen Ordnungen}{}{}
\mathkor {} {n = \operatorname{ord} \, (x)} {und} {m = \operatorname{ord} \, (y)} {,}
wobei
\mathkor {} {n} {und} {m} {}
\definitionsverweis {teilerfremd}{}{}
seien.}
\faktfolgerung {Dann hat $xy$ die Ordnung $nm$.}
\faktzusatz {}
\faktzusatz {}
}
{
Sei
\mavergleichskette
{\vergleichskette
{ (xy)^k
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir haben zu zeigen, dass $k$ ein Vielfaches von $nm$ ist. Es ist
\mavergleichskettedisp
{\vergleichskette
{1
}
{ =} { { \left( x^ky^k \right) }^n
}
{ =} { x^{kn}y^{kn}
}
{ =} { y^{kn}
}
{ } {
}
}
{}{}{,}
da ja $n$ die Ordnung von $x$ ist. Aus dieser Gleichung erhält man, dass $kn$ ein Vielfaches der Ordnung von $y$, also von $m$ sein muss. Da
\mathkor {} {n} {und} {m} {}
teilerfremd sind, folgt aus
Fakt *****,
dass $k$ ein Vielfaches von $m$ ist. Ebenso ergibt sich, dass $k$ ein Vielfaches von $n$ ist, so dass $k$, wieder aufgrund der Teilerfremdheit, ein Vielfaches von $nm$ sein muss.
\inputdefinition
{}
{
Der \definitionswort {Exponent}{}
\mathl{\exp { \left( G \right) }}{} einer endlichen Gruppe $G$ ist die kleinste positive Zahl $n$ mit der Eigenschaft, dass
\mavergleichskette
{\vergleichskette
{x^n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mathl{x \in G}{} ist.
}
\inputfaktbeweis
{Gruppentheorie/Zyklische Gruppe/Exponentenkriterium/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $G$ eine endliche
\definitionsverweis {kommutative Gruppe}{}{}
und sei
\mavergleichskette
{\vergleichskette
{ \operatorname{exp} (G)
}
{ = }{ \operatorname {ord} { { \left( G \right) } }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei
\mathl{\operatorname{exp}(G)}{} den
\definitionsverweis {Exponenten}{}{}
der Gruppe bezeichnet.}
\faktfolgerung {Dann ist $G$
\definitionsverweis {zyklisch}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Sei
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} { \operatorname{ord} \, (G)
}
{ =} {p_1^{r_1} \cdots p_k^{r_k}
}
{ } {
}
{ } {
}
}
{}{}{}
die Primfaktorzerlegung der Gruppenordnung. Der
\definitionsverweis {Exponent}{}{}
der Gruppe ist
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{exp}(G)
}
{ =} { \operatorname{kgV}( \operatorname{ord}(x):\, x \in G)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es sei $p_i$ ein Primteiler von $n$. Wegen
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{exp}(G)
}
{ =} { \operatorname{ord} \, (G)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt es ein Element
\mathl{x \in G}{,} dessen Ordnung ein Vielfaches von
\mathl{p_i^{r_i}}{} ist. Dann gibt es auch
\zusatzklammer {in der von $x$ erzeugten zyklischen Untergruppe} {} {}
ein Element $x_i$ der Ordnung
\mathl{p_i^{r_i}}{.} Dann hat das Produkt
\mathl{x_1 \cdots x_k \in G}{} nach
Lemma 4.14
die Ordnung $n$.