Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 4/latex
\setcounter{section}{4}
\zwischenueberschrift{Das Lemma von Bezout}
\inputfaktbeweis
{Teilbarkeitstheorie (Z)/Lemma von Bezout/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Jede Menge von ganzen Zahlen
\mathl{a_1 , \ldots , a_n}{}}
\faktfolgerung {besitzt einen größten gemeinsamen Teiler $d$, und dieser lässt sich als Linearkombination der
\mathl{a_1 , \ldots , a_n}{} darstellen, d.h. es gibt ganze Zahlen
\mathl{r_1 , \ldots , r_n}{} mit
\mavergleichskettedisp
{\vergleichskette
{ r_1a_1+r_2a_2 + \cdots +r_na_n
}
{ =} {d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {Insbesondere gibt es zu teilerfremden ganzen Zahlen
\mathl{a_1 , \ldots , a_n}{} eine Darstellung der $1$.}
\faktzusatz {}
}
{
Man beachte, dass ein größter gemeinsamer Teiler, der nach dem Lemma von Bézout existiert, nicht eindeutig bestimmt ist. Denn ebenso ist mit $g$ auch das Negative $-g$ ein größter gemeinsamer Teiler. Häufig wählt man den Vertreter $\geq 0$, um Eindeutigkeit zu erreichen, und spricht dann von dem \stichwort {größten gemeinsamer Teiler} {} der
\mathl{a_1 , \ldots , a_n}{.} Diese Zahl wird dann mit
\mathdisp {\operatorname{ggT} \, (a_1 , \ldots , a_n)} { }
bezeichnet. Wir besprechen nun, wie man algorithmisch zu vorgegebenen ganzen Zahlen den $\operatorname{ggT} \,$ finden kann.
\zwischenueberschrift{Der Euklidische Algorithmus}
Es seien $a,b$ ganze Zahlen,
\mavergleichskette
{\vergleichskette
{b
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann kann man die Division mit Rest durchführen und erhält
\mathkor {} {a=qb+r} {mit} {0 \leq r< \betrag { b }} {.}
Danach kann man
\zusatzklammer {bei
\mavergleichskettek
{\vergleichskettek
{r
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {}
die Division mit Rest von $b$ durch $r$ durchführen, d.h. $b$ nimmt die Rolle von $a$ und $r$ die Rolle von $b$ ein und erhält einen neuen Rest. Dies kann man fortsetzen, und da dabei die Reste immer kleiner werden bricht das Verfahren irgendwann ab.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Euklid-von-Alexandria_1.jpg} }
\end{center}
\bildtext {Euklid (4. Jahrhundert v. C.)} }
\bildlizenz { Euklid-von-Alexandria 1.jpg } {unbekannt} {Luestling} {Commons} {PD} {http://www.bath.ac.uk/~ma1dp/Biography.html}
\inputdefinition
{}
{
Es seien zwei ganze Zahlen
\mathl{a,b}{}
\zusatzklammer {mit
\mavergleichskettek
{\vergleichskettek
{b
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {}
gegeben. Dann nennt man die durch die Anfangsbedingungen
\mathkor {} {r_0= a} {und} {r_1= b} {}
und die mittels
der Division mit Rest
\mavergleichskettedisp
{\vergleichskette
{ r_{i}
}
{ =} { q_i r_{i+1} + r_{i+2}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
rekursiv bestimmte Folge $r_i$ die \definitionswort {Folge der euklidischen Reste}{.}
}
\inputfaktbeweis
{Euklidischer Algorithmus/Z/ggT/Invarianz/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Es seien ganze Zahlen
\mathkor {} {r_0= a} {und} {r_1= b \neq 0} {}
gegeben.}
\faktfolgerung {Dann besitzt die Folge
\mathbed {r_i} {}
{i=0,1,2, \ldots} {}
{,} {} {} {}
der
\definitionsverweis {euklidischen Reste}{}{}
folgende Eigenschaften.
\aufzaehlungvier{Es ist
\mathkor {} {r_{i+2} =0} {oder} {r_{i+2} < r_{i+1}} {\zusatzfussnote {Für
\mavergleichskette
{\vergleichskette
{ i
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Da $b$ auch negativ sein könnte ist dies bei
\mavergleichskette
{\vergleichskette
{ i
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
als
\mavergleichskette
{\vergleichskette
{ r_2
}
{ < }{ \betrag { r_1 }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zu lesen} {.} {.}}
}{Es gibt ein (minimales)
\mathkor {} {k \geq 2} {mit} {r_k= 0} {.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ ggT} (r_{i-1} ,r_{i})
}
{ =} { \operatorname{ggT} (r_{i} ,r_{i+1})
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{i
}
{ = }{1 , \ldots , k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
}{Sei
\mavergleichskette
{\vergleichskette
{k
}
{ \geq }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
der erste Index derart, dass
\mavergleichskette
{\vergleichskette
{r_k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Dann ist
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ggT}(a,b)
}
{ =} {r_{k-1}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungvier{Dies folgt unmittelbar aus der Definition der Division mit Rest.
}{Solange
\mavergleichskette
{\vergleichskette
{r_i
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, wird die Folge der natürlichen Zahlen $r_i$ immer kleiner, sodass irgendwann der Fall
\mavergleichskette
{\vergleichskette
{r_i
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eintreten muss.
}{Wenn $t$ ein gemeinsamer Teiler von
\mathkor {} {r_{i}} {und von} {r_{i+1}} {}
ist, so zeigt die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ r_{i-1}
}
{ =} { q_{i-1} r_{i} + r_{i+1}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
dass $t$ auch ein Teiler von $r_{i-1}$ und damit ein gemeinsamer Teiler von
\mathl{r_{i-1}}{} und von $r_{i}$ ist. Die Umkehrung folgt genauso.
}{Dies folgt aus (3) mit der Gleichungskette
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ ggT} (a,b)
}
{ =} { \operatorname{ ggT} (b,r_2)
}
{ =} { \operatorname{ ggT} (r_2,r_3)
}
{ =} { \ldots
}
{ =} { \operatorname{ ggT} (r_{k-2},r_{k-1})
}
}
{
\vergleichskettefortsetzung
{ =} { \operatorname{ ggT} (r_{k-1},r_{k})
}
{ =} { \operatorname{ ggT} (r_{k-1},0)
}
{ =} { r_{k-1}
}
{ } {}
}{}{.}
}
\inputbeispiel
{}
{
\inputaufgabeloesungvar{
Bestimme in $\Z$ mit Hilfe des euklidischen Algorithmus den \definitionsverweis {größten gemeinsamen Teiler}{}{} von $71894$ und $45327$.
} {
Der Euklidische Algorithmus liefert:
\mathdisp {71894 = 1 \cdot 45327 + 26567} { }
\mathdisp {45327 = 1 \cdot 26567 + 18760} { }
\mathdisp {26567 = 1 \cdot 18760 + 7807} { }
\mathdisp {18760 = 2 \cdot 7807 + 3146} { }
\mathdisp {7807 = 2 \cdot 3146 + 1515} { }
\mathdisp {3146 = 2 \cdot 1515 + 116} { }
\mathdisp {1515 = 13 \cdot 116 + 7} { }
\mathdisp {116 = 16 \cdot 7 + 4} { }
\mathdisp {7 = 1 \cdot 4 + 3} { }
\mathdisp {4 = 1 \cdot 3 + 1} { . }
Die Zahlen
\mathkor {} {71894} {und} {45327} {}
sind also teilerfremd.
}
}
Bei kleinen Zahlen sieht man häufig relativ schnell direkt, was ihr größter gemeinsamer Teiler ist, da man die Primfaktorzerlegung kennt bzw. mögliche gemeinsame Teiler schnell übersehen kann. Bei zwei größeren Zahlen müssten aber viel zu viele Probedivisionen durchgeführt werden! Der euklidische Algorithmus ist also zur Bestimmung des größten gemeinsamen Teilers ein sehr effektives Verfahren!
\zwischenueberschrift{Darstellung des größten gemeinsamen Teilers}
Mit dem euklidischen Algorithmus kann man auch durch Zurückrechnen eine Darstellung des größten gemeinsamen Teilers als Linearkombination der beiden vorgegebenen Zahlen erhalten. Dazu seien
\mavergleichskettedisp
{\vergleichskette
{ r_i
}
{ =} {q_ir_{i+1} + r_{i+2}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die Gleichungen im euklidischen Algorithmus und
\mavergleichskette
{\vergleichskette
{ r_{k-1}
}
{ = }{\operatorname{ggT} \,(r_0,r_1)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Aus der letzten Gleichung
\mavergleichskettedisp
{\vergleichskette
{ r_{k-3}
}
{ =} {q_{k-3} r_{k-2} + r_{k-1}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
erhält man die Darstellung
\mavergleichskettedisp
{\vergleichskette
{ r_{k-1}
}
{ =} {r_{k-3} -q_{k-3} r_{k-2}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
von $r_{k-1}$ als Linearkombination mit \mathkor {} {r_{k-3}} {und} {r_{k-2}} {.} Mit der vorhergehenden Zeile
\mavergleichskettedisp
{\vergleichskette
{ r_{k-4}
}
{ =} {q_{k-4} r_{k-3} + r_{k-2}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
bzw.
\mavergleichskettedisp
{\vergleichskette
{ r_{k-2}
}
{ =} { r_{k-4} -q_{k-4} r_{k-3}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
kann man in dieser Darstellung $r_{k-2}$ ersetzen und erhält eine Darstellung von $r_{k-1}$ als Linearkombination von
\mathkor {} {r_{k-3}} {und} {r_{k-4}} {.}
So fortfahrend erhält man schließlich eine Darstellung von
\mavergleichskettedisp
{\vergleichskette
{ r_{k-1}
}
{ =} {\operatorname{ggT} \,(r_0,r_1)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
als Linearkombination von
\mathkor {} {r_0} {und} {r_1} {.}
\inputbeispiel{}
{
Wir wollen für
\mathkor {} {52} {und} {30} {} eine Darstellung des größten gemeinsamen Teilers finden. Wir führen dazu den euklidischen Algorithmus durch.
\mathdisp {52 = 1 \cdot 30 + 22} { }
\mathdisp {30 = 1 \cdot 22 + 8} { }
\mathdisp {22 = 2 \cdot 8 + 6} { }
\mathdisp {8 = 1 \cdot 6 + 2} { }
\mathdisp {6 = 3 \cdot 2 + 0} { . }
D.h. $2$ ist der größte gemeinsame Teiler von
\mathkor {} {52} {und} {30} {.} Rückwärts gelesen erhält man daraus die Darstellung
\mavergleichskettealign
{\vergleichskettealign
{2
}
{ =} {8-6
}
{ =} {8-(22- 2 \cdot 8 )
}
{ =} {3 \cdot 8 -22
}
{ =} {3 \cdot (30-22) -22
}
}
{
\vergleichskettefortsetzungalign
{ =} {3 \cdot 30 - 4 \cdot 22
}
{ =} {3 \cdot 30 - 4 \cdot (52-30)
}
{ =} {7 \cdot 30 -4 \cdot 52
}
{ } {}
}
{}{.}
}
\zwischenueberschrift{Gemeinsame Vielfache}
Nachdem wir schon die gemeinsamen Teiler von ganzen Zahlen behandelt haben, wenden wir uns einem verwandten Begriff zu, der ebenfalls aus der Schule bekannt ist, nämlich dem des kleinsten gemeinsamen Vielfachen von ganzen Zahlen. In der Schule wird dabei \anfuehrung{kleinste}{} in Bezug auf die $\leq$-Ordnung verstanden. Wir benutzen einen äquivalenten Begriff, der sich besser auf eine weit allgemeinere Situation übertragen lässt.
\inputdefinition
{}
{
Zu einer Menge von ganzen Zahlen
\mathdisp {a_1 , \ldots , a_n} { }
heißt eine ganze Zahl $b$ ein \definitionswort {gemeinsames Vielfaches}{,} wenn $b$ ein Vielfaches von jedem $a_i$ ist, also von jedem $a_i$
\definitionsverweis {geteilt}{}{}
wird. Die Zahl $b$ heißt ein \definitionswort {kleinstes gemeinsames Vielfaches}{} der
\mathl{a_1 , \ldots , a_n}{,} wenn $b$ ein gemeinsames Vielfaches ist und wenn jedes andere gemeinsame Vielfache ein Vielfaches von $b$ ist.
}
Wir werden gleich sehen, dass es stets ein kleinstes gemeinsames Vielfaches gibt, und dass dieses, wenn man es $\geq 0$ wählt, auch eindeutig bestimmt ist. Man spricht dann einfach von
\betonung{dem}{} kleinsten gemeinsamen Vielfachen, geschrieben
\mathl{\operatorname{ kgV} \, ( a_1 , \ldots , a_n)}{.}
\inputfaktbeweis
{Teilbarkeitstheorie (Z)/Durchschnitt von Untergruppen/Durch kgV erzeugt/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Zu einer Menge von ganzen Zahlen
\mathl{a_1 , \ldots , a_n}{}}
\faktfolgerung {existiert genau ein
\definitionsverweis {kleinstes gemeinsames Vielfaches}{}{}
$\geq 0$,}
\faktzusatz {und zwar ist
\mathl{\operatorname{kgV} \, (a_1 , \ldots , a_n )}{} der eindeutig bestimmte Erzeuger
\mathl{b \geq 0}{} der Untergruppe
\mathdisp {\Z a_1 \cap \ldots \cap \Z a_n} { . }
}
\faktzusatz {}
}
{
Es ist klar, dass eine ganze Zahl $b$ ein gemeinsames Vielfaches der
\mathl{a_1 , \ldots , a_n}{} ist genau dann, wenn
\mathdisp {b \in \Z a_1 \cap \ldots \cap \Z a_n \text{ bzw. } \Z b \subseteq \Z a_1 \cap \ldots \cap \Z a_n} { }
gilt. Nach
Satz 3.2
gibt es ein eindeutig bestimmtes
\mathl{c \geq 0}{} mit
\mavergleichskettedisp
{\vergleichskette
{ \Z c
}
{ =} { \Z a_1 \cap \ldots \cap \Z a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Nach der Vorüberlegung ist daher $c$ ein gemeinsames Vielfaches und für jedes weitere gemeinsame Vielfache $b$ gilt
\mavergleichskettedisp
{\vergleichskette
{ \Z b
}
{ \subseteq} { \Z c
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dies bedeutet, dass $b$ ein Vielfaches von $c$ ist.
\inputfaktbeweis
{Teilbarkeitstheorie (Z)/Beziehungen zwischen ggT und kgV/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Für natürliche Zahlen $a,b,g$ gelten folgende Aussagen.}
\faktfolgerung {\aufzaehlungvier{Für teilerfremde $a,b$ ist
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{kgV} \, (a,b)
}
{ =} { ab
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Es gibt
\mavergleichskette
{\vergleichskette
{c,d
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathdisp {a= c \cdot \operatorname{ggT} \, (a,b) \text{ und } b= d \cdot \operatorname{ggT} \, (a,b)} { , }
wobei $c,d$ teilerfremd sind.
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{kgV} \, (ga,gb)
}
{ =} { g\cdot \operatorname{kgV} \, (a,b)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ggT} \, (a,b) \cdot \operatorname{kgV} \,(a,b)
}
{ =} { ab
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungvier{Zunächst ist natürlich das Produkt $ab$ ein gemeinsames Vielfaches von $a$ und $b$. Es sei also $f$ irgendein gemeinsames Vielfaches, also
\mathkor {} {f=ua} {und} {f=vb} {.}
Nach
Satz 4.1
gibt es im teilerfremden Fall Zahlen
\mavergleichskette
{\vergleichskette
{r,s
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ ra+sb
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Daher ist
\mavergleichskettedisp
{\vergleichskette
{ f
}
{ =} { f \cdot 1
}
{ =} { f (ra+sb)
}
{ =} { fra +fsb
}
{ =} { vbra+uasb
}
}
{
\vergleichskettefortsetzung
{ =} { (vr+us)ab
}
{ } {}
{ } {}
{ } {}
}{}{}
ein Vielfaches von $ab$.
}{Die Existenz von $c$ und $d$ ist klar. Hätten
\mathkor {} {c} {und} {d} {}
einen gemeinsamen Teiler
\mavergleichskette
{\vergleichskette
{ e
}
{ \neq }{ 1,-1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so ergäbe sich sofort der Widerspruch, dass $e \cdot \operatorname{ggT} \,(a,b)$ ein größerer gemeinsamer Teiler von
\mathkor {} {a} {und} {b} {}
wäre.
}{Die rechte Seite ist offenbar ein gemeinsames Vielfaches von
\mathkor {} {ga} {und} {gb} {.}
Es sei $n$ ein Vielfaches der linken Seite, also ein gemeinsames Vielfaches von
\mathkor {} {ga} {und} {gb} {.}
Dann kann man
\mathkor {} {n=uga} {und} {n=vgb} {}
schreiben. Damit ist
\mavergleichskette
{\vergleichskette
{uga
}
{ = }{vgb
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit ist
\mavergleichskette
{\vergleichskette
{k
}
{ \defeq }{ ua
}
{ = }{ vb
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {bei
\mavergleichskettek
{\vergleichskettek
{ g
}
{ \neq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{;}
bei
\mavergleichskettek
{\vergleichskettek
{ g
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist die Behauptung direkt klar} {} {}
ein gemeinsames Vielfaches von
\mathkor {} {a} {und} {b} {.}
Also ist
\mavergleichskette
{\vergleichskette
{n
}
{ = }{gk
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein Vielfaches der rechten Seite.
}{Wir schreiben unter Verwendung der ersten Teile
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \operatorname{ggT} \, (a,b) \cdot \operatorname{kgV} \,(a,b)
}
{ =} { \operatorname{ggT} \, (a,b)
\cdot \operatorname{kgV} \, (c\cdot( \operatorname{ggT} \, (a,b)) , d\cdot ( \operatorname{ggT} \, (a,b)) )
}
{ =} { \operatorname{ggT} \, (a,b) \cdot\operatorname{ggT} \, (a,b)\cdot \operatorname{kgV} \,(c,d)
}
{ =} { \operatorname{ggT} \, (a,b) \cdot\operatorname{ggT} \, (a,b)\cdot cd
}
{ =} { c \cdot \operatorname{ggT} \, (a,b) \cdot d \cdot \operatorname{ggT} \, (a,b)
}
}
{
\vergleichskettefortsetzungalign
{ =} { ab
}
{ } {}
{ } {}
{ } {}
}
{}{.}
}