Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I/Vorlesung 21/latex
\setcounter{section}{21}
\epigraph { Ein guter Schüler lernt auch bei einem schlechten Lehrer ... } { }
\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.
\inputfaktbeweis
{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 {}
}
{
Nach
Aufgabe 21.25
ist der Durchschnitt der Untergruppen
\mathl{\Z a_i}{} wieder eine Untergruppe von $\Z$. Nach
Satz 20.5
gibt es ein eindeutig bestimmtes
\mavergleichskette
{\vergleichskette
{c
}
{ \geq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{ \Z a_1 \cap \ldots \cap \Z a_k
}
{ =} { \Z c
}
{ } {
}
{ } {
}
{ } {}
}
{}{}{.}
Wegen
\mavergleichskette
{\vergleichskette
{\Z c
}
{ \subseteq }{ \Z a_i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle $i$ ist $c$ ein Vielfaches von jedem $a_i$, also ein gemeinsames Vielfaches der
\mathl{a_1 , \ldots , a_k}{.} Für jedes gemeinsame Vielfache $v$ dieser Elemente gilt
\mavergleichskettedisp
{\vergleichskette
{ \Z v
}
{ \subseteq} {\Z a_1 \cap \ldots \cap \Z a_k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Zahl $c$ besitzt also die Eigenschaft, dass jedes gemeinsame Vielfache der Elemente ein Vielfaches von $c$ ist. Daher ist $c$ das kleinste gemeinsame Vielfache.
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.
\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 20.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
}
{ } {}
{ } {}
{ } {}
}
{}{.}
}
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 12.9
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 12.9
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 21.3
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
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Damit ist insbesondere zu jeder ganzen Zahl $n \neq 0$ und jeder Primzahl $p$ eindeutig bestimmt, ob $p$ in der Primfaktorzerlegung überhaupt vorkommt und wenn ja mit welchem Exponenten.
\inputdefinition
{}
{
Zu einer ganzen Zahl
\mavergleichskette
{\vergleichskette
{n
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und einer
\definitionsverweis {Primzahl}{}{}
$p$ nennt man den Exponenten, mit dem $p$ in der Primfaktorzerlegung von $n$ vorkommt, den
\definitionswortpraemath {p}{ Exponenten }{}
von $n$. Er wird mit
\mathl{\nu_p(n)}{} bezeichnet.
}
Statt Exponent spricht man auch von der \stichwort {Vielfachheit} {} oder der \stichwort {Ordnung} {} von $p$ in $n$. Wenn $p$ in der Primfaktorzerlegung nicht vorkommt, so ist
\mavergleichskettedisp
{\vergleichskette
{\nu_p(n)
}
{ =} {0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Primfaktorzerlegung einer Zahl
\mathl{n \neq 0}{} kann man damit abstrakt und kompakt als
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} { \pm \prod_p p^{\nu_p(n)}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
schreiben. Da in jeder Primfaktorzerlegung nur endlich viele Primzahlen wirklich vorkommen, ist dies ein endliches Produkt.
Zu
\mathl{n=14000}{} ist die Primfaktorzerlegung gleich
\mavergleichskettedisp
{\vergleichskette
{14000
}
{ =} { 2^4 \cdot 5^3 \cdot 7
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und somit gilt
\mavergleichskettedisp
{\vergleichskette
{\nu_2(14000)
}
{ =} {4
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
\mavergleichskettedisp
{\vergleichskette
{\nu_5(14000)
}
{ =} {3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
\mavergleichskettedisp
{\vergleichskette
{\nu_7(14000)
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{\nu_p ( 14000)
}
{ =} {0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle weiteren Primzahlen $p$.
{Teilbarkeitstheorie (Z)/Exponenten/Bewertungseigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $p$ eine
\definitionsverweis {Primzahl}{}{}
und
\maabbeledisp {\nu_p} {\Z \setminus \{0\}} { \N
} {n} { \nu_p(n)
} {,}
der zugehörige
$p$-\definitionsverweis {Exponent}{}{.}}
\faktuebergang {Dann gelten folgende Aussagen.}
\faktfolgerung {\aufzaehlungdrei{Die Zahl $p^{\nu_p(n)}$ ist die größte Potenz von $p$, die $n$ teilt.
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{\nu_p( m \cdot n)
}
{ =} { \nu_p( m ) + \nu_p( n)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{\nu_p( m + n)
}
{ =} { \operatorname{min}( \nu_p( m ) , \nu_p( n) )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {es sei
\mavergleichskette
{\vergleichskette
{m+n
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
vorausgesetzt} {} {.}
}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 21.15. }
\inputfaktbeweis
{Teilbarkeitstheorie (Z)/Exponentenkriterium/Fakt}
{Korollar}
{}
{
\faktsituation {Es seien
\mathkor {} {n} {und} {k} {} positive natürliche Zahlen.}
\faktvoraussetzung {Dann wird $n$ von $k$ genau dann geteilt,}
\faktfolgerung {wenn für jede Primzahl $p$ die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ { \exp_p(n) }
}
{ \geq} { { \exp_p(k) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.}
\faktzusatz {}
\faktzusatz {}
}
{
$(1) \Rightarrow (2)$. Aus der Beziehung
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ kt
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
in Verbindung mit der eindeutigen Primfaktorzerlegung,
dass die Primfaktoren von $k$ mit mindestens ihrer Vielfachheit auch in $n$ vorkommen müssen.
$(2) \Rightarrow (1)$. Wenn die Exponentenbedingung erfüllt ist, so ist
\mavergleichskette
{\vergleichskette
{ t
}
{ = }{ \prod_p p^{{ \exp_p(n) }-{ \exp_p(k) }}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine natürliche Zahl mit
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ kt
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Aus diesem Kriterium ergibt sich, dass man zu einer gegebenen Zahl, deren Primfaktorzerlegung vorliegt, einfach alle Teiler angeben kann. Bei
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} { p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
sind die
\zusatzklammer {positiven} {} {}
Teiler genau die Zahlen
\mathdisp {p_1^{s_1} p_2^{s_2} \cdots p_2^{s_k} \text{ mit } 0 \leq s_1 \leq r_1,\, 0 \leq s_2 \leq r_2 , \ldots , 0 \leq s_k \leq r_k} { . }
Davon gibt es
\mathl{(r_1+1)(r_2+1) \cdots (r_k+1)}{} Stück.
\inputfaktbeweis
{Zahlentheorie/Primfaktorzerlegung/KgV und ggT/Fakt}
{Korollar}
{}
{
\faktsituation {Es seien
\mathkor {} {n} {und} {m} {}
positive natürliche Zahlen mit den Primfaktorzerlegungen
\mathkor {} {n=\prod_p p^{ \exp_p(n) }} {und} {m=\prod_p p^{ \exp_p(m) }} {.}}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{
\operatorname{kgV} (n,m)
}
{ =} { \prod_p p^{\max { \left( { \exp_p(n) } , { \exp_p(m) } \right) } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ggT} (n,m)
}
{ =} { \prod_p p^ {\min { \left( { \exp_p(n) } , { \exp_p(m) } \right) } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Dies folgt direkt aus Korollar 21.7.
Für die beiden Zahlen
\mathkor {} {m=2^3 \cdot 3^2 \cdot 7^2 \cdot 11} {und} {m=2^2 \cdot 3^3 \cdot 5 \cdot 11} {}
ist beispielsweise der größte gemeinsame Teiler gleich
\mathl{2^2 \cdot 3^2 \cdot 11}{} und das kleinste gemeinsame Vielfache gleich
\mathl{2^3 \cdot 3^3 \cdot 5 \cdot 7^2 \cdot 11}{.}
| << | Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I | >> |
|---|