Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 3/latex

Aus Wikiversity

\setcounter{section}{3}






\zwischenueberschrift{Division mit Rest}

In dieser und der nächsten Vorlesung stehen die ganzen Zahlen $\Z$ im Vordergrund, wobei wir uns insbesondere für die Gruppenstruktur
\mathl{(\Z,0,+)}{} interessieren. Zu einer ganzen Zahl $d$ ist die Menge
\mavergleichskettedisp
{\vergleichskette
{ \Z d }
{ =} {{ \left\{ kd \mid k \in \Z \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{} aller Vielfachen von $d$ eine Untergruppe von $\Z$. Wir wollen zeigen, dass jede Untergruppe der ganzen Zahlen $\Z$ diese Gestalt besitzt, also von einem Element erzeugt wird.





\inputfaktbeweis
{Division mit Rest/Z/Fakt}
{Satz}
{}
{

\faktsituation {}
\faktvoraussetzung {Es sei $d$ eine fixierte positive natürliche Zahl.}
\faktfolgerung {Dann gibt es zu jeder ganzen Zahl $n$ eine eindeutig bestimmte ganze Zahl $q$ und eine eindeutig bestimmte natürliche Zahl
\mathbed {r} {}
{0 \leq r \leq d-1} {}
{} {} {} {,} mit
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} {qd+r }
{ } { }
{ } { }
{ } { }
} {}{}{.}}
\faktzusatz {}
\faktzusatz {}

}
{

\teilbeweis {Zur Existenz.\leerzeichen{}}{}{}
{Bei
\mathl{n=0}{} ist
\mathl{q=r=0}{} eine Lösung. Es sei $n$ positiv. Da $d$ positiv ist, gibt es ein Vielfaches
\mathl{ad \geq n}{.} Daher gibt es auch eine Zahl $q$ mit \mathkon { qd \leq n } { und } { (q+1)d > n }{ .} Es sei
\mathl{r:=n-qd}{.} Dann ist
\mavergleichskettedisp
{\vergleichskette
{qd }
{ \leq} { qd+r }
{ <} {qd+d }
{ } { }
{ } { }
} {}{}{} und daher ist
\mathl{0 \leq r <d}{} wie gewünscht. Bei $n$ negativ kann man schreiben
\mathl{-n=\tilde{q} d+\tilde{r}}{} nach dem Resultat für positive Zahlen. Daraus ergibt sich
\mathdisp {n= (-\tilde{q})d -\tilde{r} = \begin{cases} (-\tilde{q}) d+0 \text{ bei } \tilde{r}=0 \\ (- \tilde{q} -1)d +d - \tilde{r} \text{ sonst}\, . \end{cases}} { }
Im zweiten Fall erfüllen \mathkor {} {q=- \tilde{q} -1} {und} {r=d - \tilde{r}} {} die Bedingungen.}
{} \teilbeweis {Zur Eindeutigkeit.\leerzeichen{}}{}{}
{Es sei
\mathl{qd+r=n= \tilde{q}d + \tilde{r}}{,} wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung
\mathl{\tilde{r} \geq r}{.} Dann gilt
\mathl{(q-\tilde{q})d = \tilde{r} -r}{.} Diese Differenz ist nichtnegativ und kleiner als $d$, links steht aber ein Vielfaches von $d$, so dass die Differenz $0$ sein muss und die beiden Darstellungen überein stimmen.}
{}

}


In der Notation des vorstehenden Satzes soll $q$ an \stichwort {Quotient} {} und $r$ an \stichwort {Rest} {} erinnern. Die Division mit Rest kann man auch so verstehen, dass man jede rationale Zahl $n/d$ als
\mavergleichskettedisp
{\vergleichskette
{ \frac{n}{d} }
{ =} { \lfloor \frac{n}{d} \rfloor + \frac{r}{d} }
{ } { }
{ } { }
{ } { }
} {}{}{} schreiben kann, wobei
\mathl{\lfloor s \rfloor}{} die größte ganze Zahl $\leq s$ bedeutet und der rationale Rest $r/d$ die Bedingungen
\mathl{0 \leq r/d <1}{} erfüllt. In dieser Form kann man auch eine Division mit Rest für jede reelle Zahl aus den Axiomen der reellen Zahlen beweisen.





\inputfaktbeweis
{Untergruppen von Z/Ein Erzeuger/Fakt}
{Satz}
{}
{

\faktsituation {}
\faktvoraussetzung {Die \definitionsverweis {Untergruppen}{}{} von $\Z $ sind genau}
\faktfolgerung {die Teilmengen der Form
\mavergleichskettedisp
{\vergleichskette
{ \Z d }
{ =} { { \left\{ kd \mid k \in \Z \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{} mit einer eindeutig bestimmten nichtnegativen Zahl $d$.}
\faktzusatz {}
\faktzusatz {}

}
{

Eine Teilmenge der Form $\Z d$ ist aufgrund der Distributivgesetze eine Untergruppe. Es sei umgekehrt
\mavergleichskette
{\vergleichskette
{H }
{ \subseteq }{ \Z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Untergruppe. Bei
\mavergleichskette
{\vergleichskette
{H }
{ = }{ 0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} kann man
\mavergleichskette
{\vergleichskette
{d }
{ = }{ 0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} nehmen, so dass wir voraussetzen dürfen, dass $H$ neben $0$ noch mindestens ein weiteres Element $x$ enthält. Wenn $x$ negativ ist, so muss die Untergruppe $H$ auch das Negative davon, also $-x$ enthalten, welches positiv ist. D.h. $H$ enthält auch positive Zahlen. Es sei nun $d$ die kleinste positive Zahl aus $H$. Wir behaupten
\mavergleichskette
{\vergleichskette
{H }
{ = }{\Z d }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Dabei ist die Inklusion
\mavergleichskette
{\vergleichskette
{ \Z d }
{ \subseteq }{H }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} klar, da mit $d$ alle \zusatzklammer {positiven und negativen} {} {} Vielfachen von $d$ dazugehören müssen. Für die umgekehrte Inklusion sei
\mavergleichskette
{\vergleichskette
{h }
{ \in }{H }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} beliebig. Nach der Division mit Rest gilt
\mathdisp {h=qd+r \text{ mit } 0 \leq r < d} { . }
Wegen \mathkon { h \in H } { und } { qd \in H }{ } ist auch
\mavergleichskette
{\vergleichskette
{ r }
{ = }{ h-qd }
{ \in }{ H }
{ }{ }
{ }{ }
} {}{}{.} Nach der Wahl von $d$ muss wegen
\mavergleichskette
{\vergleichskette
{r }
{ < }{d }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gelten:
\mavergleichskette
{\vergleichskette
{r }
{ = }{ 0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} Dies bedeutet
\mavergleichskette
{\vergleichskette
{h }
{ = }{qd }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und damit
\mavergleichskette
{\vergleichskette
{h }
{ \in }{\Z d }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} also
\mavergleichskette
{\vergleichskette
{H }
{ \subseteq }{\Z d }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

}


Bevor wir uns fragen, wie man zu einer durch verschiedene Zahlen erzeugte Untergruppe einen einzigen Erzeuger findet, besprechen wir einige Folgerungen für endliche Gruppen.




\inputfaktbeweis
{Gruppenelement/Neutrale Potenzen und Ordnung/Fakt}
{Lemma}
{}
{

\faktsituation {}
\faktvoraussetzung {Es sei $G$ eine \definitionsverweis {Gruppe}{}{} und $x \in G$ ein Element mit endlicher \definitionsverweis {Ordnung}{}{}
\mathl{d= \operatorname{ord} \, (x)}{.}}
\faktfolgerung {Dann ist die Menge
\mavergleichskettedisp
{\vergleichskette
{M }
{ =} { { \left\{ k \in \Z \mid x^k = e_G \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{} eine Untergruppe von $\Z$, die von $d$ erzeugt wird.}
\faktzusatz {}
\faktzusatz {}

}
{

Es ist einfach zu sehen, dass $M$ eine Untergruppe von $\Z$ ist. Da $d$ die Ordnung von $x$ ist, gilt
\mathl{d \in M}{} und damit
\mathl{\Z d \subseteq M}{.} Nach Satz 3.2 ist
\mathl{M=\Z a}{} mit
\mathl{0 \leq a \leq d}{.} Bei
\mathl{a < d}{} wäre aber
\mathl{x^a=e}{} nach Definition von $M$ und $d$ könnte nicht die Ordnung sein.

}







\zwischenueberschrift{Endliche zyklische Gruppen}





\inputfaktbeweis
{Endliche zyklische Gruppe/Untergruppe/Ist zyklisch/Fakt}
{Satz}
{}
{

\faktsituation {}
\faktvoraussetzung {Es sei $G$ eine \definitionsverweis {zyklische Gruppe}{}{.}}
\faktfolgerung {Dann ist auch jede \definitionsverweis {Untergruppe}{}{} von $G$ zyklisch.}
\faktzusatz {}
\faktzusatz {}

}
{

Es sei $u$ ein Erzeuger von $G$, d.h. jedes Element
\mathl{z \in G}{} lässt sich darstellen als \mathkor {} {ku} {mit} {k \in \Z} {.} Es sei
\mathl{H \subseteq G}{} eine Untergruppe. Dazu definieren wir die Menge
\mavergleichskettedisp
{\vergleichskette
{ M }
{ =} { { \left\{ k \in \Z \mid ku \in H \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} Dies ist eine Untergruppe von $\Z$. Aus \mathkor {} {ku \in H} {und} {mu \in H} {} folgt sofort aufgrund von Lemma 2.2
\mavergleichskettedisp
{\vergleichskette
{(k+m)u }
{ =} {ku+mu }
{ \in} {H }
{ } {}
{ } {}
} {}{}{,} also
\mathl{k+m \in M}{.} Ebenso gehört wegen
\mavergleichskettedisp
{\vergleichskette
{(-k)u }
{ =} {-(ku) }
{ \in} {H }
{ } {}
{ } {}
} {}{}{} auch das Negative zu $M$. Daher ist nach Satz 3.2
\mathl{M=\Z d}{} mit einem eindeutig bestimmten
\mathl{d \geq 0}{.} Wir behaupten, dass
\mavergleichskettedisp
{\vergleichskette
{H }
{ =} { ( du ) }
{ } { }
{ } { }
{ } { }
} {}{}{} ist, dass also das $d$-Fache von $u$ die Untergruppe erzeugt. Wegen
\mathl{d \in M}{} ist
\mathl{du \in H}{} und die Inklusion
\mathl{(du) \subseteq H}{} klar. Es sei umgekehrt
\mathl{h \in H}{} und
\mathl{h= ku}{.} Dann ist $k=rd$ für ein $r \in \Z$ und daher
\mavergleichskettedisp
{\vergleichskette
{h }
{ =} {ku }
{ =} {(rd)u }
{ =} {r(du) }
{ } {}
} {}{}{.}

}


Die folgende Aussage gilt allgemeiner in jeder endlichen Gruppe und für jede Untergruppe, der Beweis braucht dann aber das Konzept der Nebenklassen.




\inputfaktbeweis
{Endliche zyklische Gruppe/Ordnung teilt Gruppenordnung/Fakt}
{Korollar}
{}
{

\faktsituation {}
\faktvoraussetzung {Es sei $G$ eine endliche \definitionsverweis {zyklische Gruppe}{}{} und
\mathl{x \in G}{} ein Element.}
\faktfolgerung {Dann teilt die \definitionsverweis {Ordnung}{}{} $\operatorname{ord} \, (x)$ die \definitionsverweis {Gruppenordnung}{}{} $\operatorname{ord} \, (G)$.}
\faktzusatz {}
\faktzusatz {}

}
{

Es sei $u$ ein Erzeuger von $G$. Dann ist die Ordnung von $u$ gleich der Ordnung $n$ von $G$. Wir schreiben
\mathl{x=u^m}{.} Dann ist
\mavergleichskettedisp
{\vergleichskette
{x^n }
{ =} {(u^m)^n }
{ =} {u^{mn} }
{ =} {(u^n)^m }
{ =} {e^m }
} {
\vergleichskettefortsetzung
{ =} {e }
{ } {}
{ } {}
{ } {}
}{}{.} Daher gehört die Gruppenordnung $n$ zur Menge
\mavergleichskettedisp
{\vergleichskette
{M }
{ =} { { \left\{ k \in \Z \mid x^k = e \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{.} Diese hat nach Lemma 3.3 die Gestalt
\mathl{M=\Z d}{,} wobei $d$ die Ordnung von $x$ ist. Also ist
\mathl{n \in \Z d}{} und $d$ ist ein Teiler von $n$.

}







\zwischenueberschrift{Teilbarkeitsbegriffe}

Es sei
\mathl{d_1 , \ldots , d_n}{} eine Menge von ganzen Zahlen und
\mathl{H \subseteq \Z}{} die dadurch erzeugte Untergruppe von $\Z$, also
\mavergleichskettedisp
{\vergleichskette
{H }
{ =} {( d_1 , \ldots , d_n) }
{ =} { { \left\{ a_1d_1 + \cdots + a_nd_n \mid a_i \in \Z \right\} } }
{ } { }
{ } { }
} {}{}{.} Nach den obigen Resultaten gibt es ein eindeutig bestimmtes \mathkor {} {d \in \N} {mit} {H=\Z d} {.} Wie findet man dieses $d$? Hierzu muss man vor allem den Fall von zwei Erzeugern verstehen. Denn wenn
\mavergleichskette
{\vergleichskette
{ (d_1,d_2) }
{ = }{ \Z d }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist, so ist auch
\mavergleichskettedisp
{\vergleichskette
{ (d_1 , \ldots , d_n) }
{ =} {(d,d_3 , \ldots , d_n) }
{ } { }
{ } { }
{ } { }
} {}{}{,} und die Anzahl der Erzeuger ist um eins reduziert. In diesem Zusammenhang erinnern wir an verschiedene Sprechweisen, die schon aus der Schule bekannt sind.




\inputdefinition
{}
{

Man sagt, dass die ganze Zahl $a$ die ganze Zahl $b$ \definitionswort {teilt}{} \zusatzklammer {oder dass $b$ von $a$ \definitionswort {geteilt}{} wird, oder dass $b$ ein \definitionswort {Vielfaches}{} von $a$ ist} {} {,} wenn es eine ganze Zahl $c$ derart gibt, dass
\mavergleichskette
{\vergleichskette
{b }
{ = }{ c \cdot a }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist. Man schreibt dafür auch $a {{|}} b$.

}


\inputfaktbeweis
{Teilbarkeitstheorie (Z)/Verschiedene Eigenschaften/Fakt}
{Lemma}
{}
{

\faktsituation {}
\faktvoraussetzung {In $\Z$ gelten folgende Teilbarkeitsbeziehungen.}
\faktfolgerung {\aufzaehlungsechs{Für jede ganze Zahl $a$ gilt \mathkor {} {1 \, {{|}}\, a} {und} {a \,{{|}}\, a} {.} }{Für jede ganze Zahl $a$ gilt
\mathl{a \,{{|}}\, 0}{.} }{Gilt \mathkor {} {a \,{{|}}\, b} {und} {b \,{{|}}\, c} {,} so gilt auch
\mathl{a \,{{|}}\, c}{.} }{Gilt \mathkor {} {a \,{{|}}\, b} {und} {c \,{{|}}\, d} {,} so gilt auch
\mathl{ac \,{{|}}\, bd}{.} }{Gilt
\mathl{a \,{{|}}\, b}{,} so gilt auch
\mathl{ac \,{{|}}\, bc}{} für jede ganze Zahl
\mathl{c}{.} }{Gilt \mathkor {} {a \,{{|}}\, b} {und} {a \,{{|}}\, c} {,} so gilt auch
\mathl{a \,{{|}}\, { \left( rb+sc \right) }}{} für beliebige ganze Zahlen $r,s$. }}
\faktzusatz {}
\faktzusatz {}

}
{ Siehe Aufgabe 3.6. }





\inputdefinition
{}
{

Es seien
\mathl{a_1 , \ldots , a_k}{} ganze Zahlen. Dann heißt eine ganze Zahl $t$ \definitionswort {gemeinsamer Teiler}{} der
\mathl{a_1 , \ldots , a_k}{,} wenn $t$ jedes $a_i$ teilt \zusatzklammer {
\mavergleichskettek
{\vergleichskettek
{i }
{ = }{1 , \ldots , k }
{ }{ }
{ }{ }
{ }{ }
} {}{}{}} {} {.}

Eine ganze Zahl $g$ heißt \definitionswort {größter gemeinsamer Teiler}{} der
\mathl{a_1 , \ldots , a_k}{,} wenn $g$ ein gemeinsamer Teiler ist und wenn jeder gemeinsame Teiler $t$ dieses $g$ teilt.

Die Elemente
\mathl{a_1 , \ldots , a_k}{} heißen \definitionswort {teilerfremd}{,} wenn $1$ ihr größter gemeinsamer Teiler ist.

}





\inputfaktbeweis
{Teilbarkeitstheorie (Z)/Gemeinsame Teiler/Charakterisierung mit Untergruppen/Fakt}
{Lemma}
{}
{

\faktsituation {}
\faktvoraussetzung {Es seien
\mathl{a_1 , \ldots , a_k}{} ganze Zahlen und
\mavergleichskette
{\vergleichskette
{H }
{ = }{(a_1 , \ldots , a_k ) }
{ = }{ { \left\{ n_1a_1+n_2a_2 + \cdots + n_ka_k \mid n_j \in \Z \right\} } }
{ }{ }
{ }{ }
} {}{}{} die davon \definitionsverweis {erzeugte Untergruppe}{}{.}}
\faktfolgerung {Eine ganze Zahl $t$ ist ein \definitionsverweis {gemeinsamer Teiler}{}{} der $a_1 , \ldots , a_k$ genau dann, wenn
\mavergleichskette
{\vergleichskette
{H }
{ \subseteq }{ \Z t }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist, und $t$ ist ein \definitionsverweis {größter gemeinsamer Teiler}{}{} genau dann, wenn
\mavergleichskette
{\vergleichskette
{H }
{ = }{ \Z t }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist.}
\faktzusatz {}
\faktzusatz {}

}
{

Aus
\mavergleichskette
{\vergleichskette
{ H }
{ = }{ (a_1 , \ldots , a_k ) }
{ \subseteq }{ (t) }
{ }{ }
{ }{ }
} {}{}{} folgt sofort
\mavergleichskette
{\vergleichskette
{a_i \Z }
{ \subseteq }{t \Z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} für jedes
\mavergleichskette
{\vergleichskette
{i }
{ = }{1 , \ldots , k }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} was gerade bedeutet, dass $t$ diese Zahlen teilt, also ein gemeinsamer Teiler ist. Es sei umgekehrt $t$ ein gemeinsamer Teiler. Dann ist
\mavergleichskette
{\vergleichskette
{a_i }
{ \in }{t \Z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und da
\mavergleichskette
{\vergleichskette
{H }
{ = }{(a_1 , \ldots , a_k ) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die kleinste Untergruppe ist, die alle $a_i$ enthält, muss
\mavergleichskette
{\vergleichskette
{H }
{ \subseteq }{ t \Z }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gelten.

Aufgrund von Satz 3.2 wissen wir, dass es eine ganze Zahl $g$ gibt mit
\mavergleichskette
{\vergleichskette
{H }
{ = }{\Z d }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Für einen anderen gemeinsamen Teiler $t$ der $a_i$ gilt
\mavergleichskette
{\vergleichskette
{\Z d }
{ = }{H }
{ \subseteq }{ \Z t }
{ }{ }
{ }{ }
} {}{}{,} so dass $d$ von allen anderen gemeinsamen Teilern geteilt wird, also ein größter gemeinsamer Teiler ist.

}



<< | Kurs:Einführung in die Algebra (Osnabrück 2009) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)