Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 3/latex
\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$, sodass 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 des Distributivgesetzes eine Untergruppe. Es sei umgekehrt
\mavergleichskette
{\vergleichskette
{H
}
{ \subseteq }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Untergruppe. Bei
\mavergleichskette
{\vergleichskette
{H
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
kann man
\mavergleichskette
{\vergleichskette
{d
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nehmen, sodass 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$.
}
{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
}
{ }{
}
{ }{
}
}
{}{}{,}
sodass $d$ von allen anderen gemeinsamen Teilern geteilt wird, also ein größter gemeinsamer Teiler ist.