Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 8/latex
\setcounter{section}{8}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Flickr - archer10 (Dennis) - Bolivia-91.jpg} }
\end{center}
\bildtext {Als Alternative wurde über ein Vorlesungslama ...} }
\bildlizenz { Flickr - archer10 (Dennis) - Bolivia-91.jpg } {Dennis Jarvis} {Matanya} {Commons} {CC-by-sa 2.0} {}
In dieser Vorlesung besprechen wir die Teilbarkeitsrelation innerhalb der natürlichen und der ganzen Zahlen genauer. Dies ist einerseits eine wichtige Ordnungsrelation, die darüber hinaus eng mit der additiven und der multiplikativen Struktur der ganzen Zahlen verbunden ist. Insbesondere werden wir die Untergruppen der ganzen Zahlen charakterisieren, was wiederum eine wichtige Voraussetzung für die Konstruktion von endlichen Ringen und Körpern in der zwölften Vorlesung ist, und wir werden die Eindeutigkeit der Primfaktorzerlegung in $\Z$ beweisen. Ferner führen die Überlegungen zum euklidischen Algorithmus.
\zwischenueberschrift{Das Lemma von Bezout}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Kielcanal.PNG} }
\end{center}
\bildtext {} }
\bildlizenz { Kielcanal.PNG } {} {Grunners} {Commons} {PD} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Zille vorichte.png} }
\end{center}
\bildtext {} }
\bildlizenz { Zille vorichte.png } {Heinrich Zille} {Hendrike} {Commons} {gemeinfrei} {}
\inputbeispiel{}
{
Die Wasserspedition \anfuehrung{Alles im Eimer}{} verfügt über einen $7$- und einen $10$-Liter-Eimer, die allerdings keine Markierungen haben. Sie erhält den Auftrag, insgesamt genau einen Liter Wasser von der Nordsee in die Ostsee zu transportieren. Kann sie diesen Auftrag erfüllen?
Die Aufgabe ist lösbar: Man macht dreimal den $7$-Liter-Eimer in der Nordsee voll und transportiert dies in die Ostsee. Danach
\zusatzklammer {oder gleichzeitig} {} {}
macht man zweimal den $10$-Liter-Eimer in der Ostsee voll und transportiert dies in die Nordsee. Unterm Strich hat man dann
\mavergleichskettedisp
{\vergleichskette
{3 \cdot 7 -2 \cdot 10
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Liter transportiert
\zusatzklammer {eine andere Möglichkeit ist
\mavergleichskettek
{\vergleichskettek
{5 \cdot 10 - 7 \cdot 7
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {.}
}
Die dieser Überlegung zugrunde liegende Aussage heißt \stichwort {Lemma von Bezout} {.}
{Lemma von Bezout/N/Teilerfremd/Induktion/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Es seien
\mavergleichskette
{\vergleichskette
{a,b
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zwei
\definitionsverweis {teilerfremde}{}{}
natürliche Zahlen.}
\faktfolgerung {Dann gibt es ganze Zahlen
\mavergleichskette
{\vergleichskette
{r,s
}
{ \in }{\Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ ra+sb
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{Dies wird sich weiter unten als Korollar zu
Korollar 8.5
ergeben, man kann es aber auch direkt durch Induktion über das Maximum von
\mathkor {} {a} {und} {b} {}
beweisen, siehe
Man sagt auch, dass
\mavergleichskette
{\vergleichskette
{ ra+sb
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine \stichwort {Darstellung} {} der $1$ als eine \stichwort {Linearkombination} {} der
\mathkor {} {a} {und} {b} {}
ist. Die
\mathl{r,s}{} heißen \stichwort {Koeffizienten} {} der Darstellung.
\zwischenueberschrift{Die Untergruppen von $\Z$ }
Die Division mit Rest für ganze Zahlen ist analog zur Polynomdivision.
{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 {}
{ Siehe Aufgabe 8.8. }
Wie im eingangs gegebenen Beispiel kann man sich eine Menge
\mathl{a_1 , \ldots , a_k}{} von ganzen Zahlen
\zusatzklammer {Eimergrößen} {} {}
vorgeben und sich fragen, welche Zahlen man daraus mit Hilfe von ganzzahligen Koeffizienten bilden kann
\zusatzklammer {welche Wassermengen man transportieren kann} {} {.}
Es geht also um die Menge aller Zahlen der Form
\mathdisp {n_1a_1 + \cdots + n_ka_k \text{ mit } n_j \in \Z} { . }
Diese Gesamtmenge bildet eine Untergruppe von $\Z$, siehe
Aufgabe 8.37,
man spricht von der von den
\mathl{a_1 , \ldots , a_k}{} \stichwort {erzeugten Untergruppe} {} von $\Z$. Statt Eimern kann man sich auch eine Menge von ganzzahligen Pfeilen, die man hintereinanderlegen und umdrehen kann, vorstellen, oder eine vorgegebene Menge an Sprungmöglichkeiten, oder eine Menge an Gewichten. Der folgende Satz heißt auch \anfuehrung{Ein-Eimer-Satz}{.}
\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
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
{Teilbarkeitstheorie (Z)/Gemeinsame Teiler/Charakterisierung mit Untergruppen/Fakt}
{Korollar}
{}
{
\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 {}
{ Siehe Aufgabe 8.15. }
Dies besagt insbesondere, dass es stets einen größten gemeinsamen Teiler gibt. Im teilerfremden Fall bedeutet es, dass es eine Darstellung der $1$ als ganzzahlige Linearkombination der $a_i$ gibt.
\zwischenueberschrift{Der Euklidische Algorithmus}
Der euklidische Algorithmus dient dazu, zu gegebenen Zahlen $a,b$ ihren größten gemeinsamen Teiler zu bestimmen, und eine Darstellung dieses größten gemeinsamen Teilers ale eine Linearkombination der \mathkor {} {a} {und} {b} {} explizit zu finden.
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, so dass 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{Kleinstes gemeinsames Vielfaches und größter gemeinsamer Teiler}
Zu einer ganzen Zahl $a$ besteht $\Z a$ aus allen Vielfachen von $a$. Zu zwei Zahlen $a,b$ besteht somit der Durchschnitt
\mathl{\Z a \cap \Z b}{} aus allen Zahlen, die sowohl von $a$ als auch von $b$ Vielfache sind, also aus allen gemeinsamen Vielfachen von
\mathkor {} {a} {und} {b} {.}
In der Tat gilt die folgende Aussage.
{Z/Durchschnitt von Untergruppen/KgV/Fakt}
{Lemma}
{}
{
\faktsituation {Es seien
\mathl{a_1 , \ldots , a_k}{} ganze Zahlen.}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{ \Z a_1 \cap \Z a_2 \cap \ldots \cap \Z a_k
}
{ =} { \Z u
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei $u$ das
\definitionsverweis {kleinste gemeinsame Vielfache}{}{}
der
\mathl{a_1 , \ldots , a_k}{} ist.}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 8.27. }
Für ganze Zahlen setzen wird den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache stets positiv an, um Eindeutigkeit zu erzielen. Grundsätzlich hat jeweils das Negative dazu die gleichen Eigenschaften.
{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 {}
{ Siehe Aufgabe 8.28. }
Der Teil (4) der vorstehenden Aussage erlaubt es, das kleinste gemeinsame Vielfache zu zwei Zahlen algorithmisch dadurch zu bestimmen, dass man ihren größten gemeinsamen Teiler mit Hilfe des euklidischen Algorithmus bestimmt und das Produkt durch diesen teilt.
\zwischenueberschrift{Der Hauptsatz der elementaren Zahlentheorie}
Wir möchten nun zur Primfaktorzerlegung, deren Existenz wir bereits in
Satz 2.6 (Mathematik für Anwender (Osnabrück 2023-2024))
gezeigt haben, beweisen, dass sie eindeutig ist. Natürlich kann man
\mavergleichskettedisp
{\vergleichskette
{12
}
{ =} {3 \cdot 2 \cdot 2
}
{ =} {2 \cdot 3 \cdot 2
}
{ =} {2 \cdot 2 \cdot 3
}
{ } {
}
}
{}{}{}
schreiben, mit eindeutig ist also eindeutig bis auf die Reihenfolge gemeint. Um dies zu zeigen brauchen wir zunächst das sogenannte \stichwort {Lemma von Euklid} {,} das eine wichtige Eigenschaft einer Primzahl beschreibt.
\inputfaktbeweis
{Teilbarkeitstheorie (Z)/Primzahl erfüllt Primelementeigenschaft/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $p$ eine
\definitionsverweis {Primzahl}{}{}
und}
\faktvoraussetzung {$p$ teile ein Produkt $ab$ von natürlichen Zahlen
\mavergleichskette
{\vergleichskette
{a,b
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann teilt $p$ einen der Faktoren.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir setzen voraus, dass $a$ kein Vielfaches von $p$ ist
\zusatzklammer {andernfalls sind wir fertig} {} {.}
Dann müssen wir zeigen, dass $b$ ein Vielfaches von $p$ ist. Unter der gegebenen Voraussetzung sind
\mathkor {} {a} {und} {p} {}
\definitionsverweis {teilerfremd}{}{.}
Nach
dem Lemma von Bezout
gibt es ganze Zahlen
\mathl{r,s}{} mit
\mavergleichskettedisp
{\vergleichskette
{ ra +sp
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Da
\mathl{ab}{} ein Vielfaches von $p$ ist, gibt es ein $t$ mit
\mavergleichskettedisp
{\vergleichskette
{ab
}
{ =} {tp
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Daher ist
\mavergleichskettedisp
{\vergleichskette
{ b
}
{ =} { b \cdot 1
}
{ =} { b (ra +sp)
}
{ =} { ab r + bs p
}
{ =} { t p r +bsp
}
}
{
\vergleichskettefortsetzung
{ =} { p { \left( tr +bs \right) }
}
{ } {}
{ } {}
{ } {}
}{}{.}
Also ist $b$ ein Vielfaches von $p$.
Aus dem Lemma von Euklid folgt sofort die etwas stärkere Aussage: Wenn eine Primzahl $p$ ein beliebiges Produkt
\mathl{a_1 a_2 { \cdots } a_n}{} teilt, dann teilt $p$ mindestens einen Faktor. Man wendet das Lemma einfach auf
\mathl{(a_1 a_2 { \cdots } a_{n-1}) \cdot a_n}{} an
\zusatzklammer {formal ist das eine Induktion über die Anzahl der Faktoren} {} {.}
Dies wird im Beweis des folgenden \stichwort {Hauptsatzes der elementaren Zahlentheorie} {} verwendet.
\inputfaktbeweis
{Zahlentheorie/Primfaktorzerlegung/Fakt}
{Satz}
{}
{
Jede natürliche Zahl
\mathbed {n\in \N} {}
{n \geq 2} {}
{} {} {} {,}
besitzt eine eindeutige Zerlegung in Primfaktoren.
D.h. es gibt eine Darstellung
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {p_1 { \cdots } p_r
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\definitionsverweis {Primzahlen}{}{}
$p_i$, und dabei sind die Primfaktoren bis auf ihre Reihenfolge eindeutig bestimmt.
}
{
Die Existenz der Primfaktorzerlegung wurde bereits in
Satz 2.6 (Mathematik für Anwender (Osnabrück 2023-2024))
gezeigt.
Die Eindeutigkeit wird durch Induktion über $n$ gezeigt. Für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
liegt eine Primzahl vor. Sei nun
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {p_1 { \cdots } p_r
}
{ =} {q_1 { \cdots } q_s
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl $p_1$ das Produkt rechts teilt. Nach
Satz 6.12
muss dann $p_1$ einen der Faktoren rechts teilen. Nach Umordnung können wir annehmen, dass $q_1$ von $p_1$ geteilt wird. Da $q_1$
selbst eine Primzahl ist, folgt, dass
\mavergleichskette
{\vergleichskette
{p_1
}
{ = }{q_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sein muss. Daraus ergibt sich durch Kürzen, dass
\mavergleichskettedisp
{\vergleichskette
{ p_2 { \cdots } p_r
}
{ =} {q_2 { \cdots } q_s
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist. Nennen wir diese Zahl $n'$. Da
\mavergleichskette
{\vergleichskette
{n'
}
{ < }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, können wir die Induktionsvoraussetzung auf $n'$ anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen.
In der \stichwort {kanonischen Primfaktorzerlegung} {} schreibt man die beteiligten Primzahlen in aufsteigender Reihenfolge mit ihrem jeweiligen Exponenten, also beispielsweise
\mavergleichskettedisp
{\vergleichskette
{ 840
}
{ =} { 2^3 \cdot 3 \cdot 5 \cdot 7
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}