Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I/Vorlesung 21/kontrolle

„Ein guter Schüler lernt auch bei einem schlechten Lehrer ...“

Kleinstes gemeinsames Vielfaches und größter gemeinsamer Teiler

Zu einer ganzen Zahl ${}a$ besteht ${}\mathbb {Z} a$ aus allen Vielfachen von ${}a$. Zu zwei Zahlen ${}a,b$ besteht somit der Durchschnitt ${}\mathbb {Z} a\cap \mathbb {Z} b$ aus allen Zahlen, die sowohl von ${}a$ als auch von ${}b$ Vielfache sind, also aus allen gemeinsamen Vielfachen von ${}a$ und ${}b$. In der Tat gilt die folgende Aussage.

Lemma Referenznummer erstellen

Es seien ${}a_{1},\ldots ,a_{k}$ ganze Zahlen.

Dann ist

${}\mathbb {Z} a_{1}\cap \mathbb {Z} a_{2}\cap \ldots \cap \mathbb {Z} a_{k}=\mathbb {Z} u\,,$

wobei ${}u$ das kleinste gemeinsame Vielfache der ${}a_{1},\ldots ,a_{k}$ ist.

Beweis

Nach Aufgabe 20.14 ist der Durchschnitt der Untergruppen ${}\mathbb {Z} a_{i}$ wieder eine Untergruppe von ${}\mathbb {Z}$. Nach Satz 20.5 gibt es ein eindeutig bestimmtes ${}c\geq 0$ mit

${}\mathbb {Z} a_{1}\cap \ldots \cap \mathbb {Z} a_{k}=\mathbb {Z} c\,.$

Wegen ${}\mathbb {Z} c\subseteq \mathbb {Z} a_{i}$ für alle ${}i$ ist ${}c$ ein Vielfaches von jedem ${}a_{i}$, also ein gemeinsames Vielfaches der ${}a_{1},\ldots ,a_{k}$. Für jedes gemeinsame Vielfache ${}v$ dieser Elemente gilt

${}\mathbb {Z} v\subseteq \mathbb {Z} a_{1}\cap \ldots \cap \mathbb {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.

$\Box$

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.

Lemma Referenznummer erstellen

Für natürliche Zahlen ${}a,b,g$ gelten folgende Aussagen.

1. Für teilerfremde ${}a,b$ ist

   ${}\operatorname {kgV} \,(a,b)=ab\,.$

2. Es gibt ${}c,d\in \mathbb {Z}$ mit

   $a=c\cdot \operatorname {ggT} \,(a,b)\,\,{\text{ und }}\,\,b=d\cdot \operatorname {ggT} \,(a,b),$

   wobei ${}c,d$ teilerfremd sind.

3. Es ist

   ${}\operatorname {kgV} \,(ga,gb)=g\cdot \operatorname {kgV} \,(a,b)\,.$

4. Es ist

   ${}\operatorname {ggT} \,(a,b)\cdot \operatorname {kgV} \,(a,b)=ab\,.$

Beweis

1. Zunächst ist natürlich das Produkt ${}ab$ ein gemeinsames Vielfaches von ${}a$ und ${}b$. Es sei also ${}f$ irgendein gemeinsames Vielfaches, also ${}f=ua$ und ${}f=vb$. Nach Satz 20.1 gibt es im teilerfremden Fall Zahlen ${}r,s\in \mathbb {Z}$ mit ${}ra+sb=1$. Daher ist

   ${}f=f\cdot 1=f(ra+sb)=fra+fsb=vbra+uasb=(vr+us)ab\,$

   ein Vielfaches von ${}ab$.

2. Die Existenz von ${}c$ und ${}d$ ist klar. Hätten ${}c$ und ${}d$ einen gemeinsamen Teiler ${}e\neq 1,-1$, so ergäbe sich sofort der Widerspruch, dass ${}e\cdot \operatorname {ggT} \,(a,b)$ ein größerer gemeinsamer Teiler von ${}a$ und ${}b$ wäre.
3. Die rechte Seite ist offenbar ein gemeinsames Vielfaches von ${}ga$ und ${}gb$. Es sei ${}n$ ein Vielfaches der linken Seite, also ein gemeinsames Vielfaches von ${}ga$ und ${}gb$. Dann kann man ${}n=uga$ und ${}n=vgb$ schreiben. Damit ist ${}uga=vgb$ und somit ist ${}k:=ua=vb$ (bei ${}g\neq 0$; bei ${}g=0$ ist die Behauptung direkt klar) ein gemeinsames Vielfaches von ${}a$ und ${}b$. Also ist ${}n=gk$ ein Vielfaches der rechten Seite.
4. Wir schreiben unter Verwendung der ersten Teile

   ${}{\begin{aligned}\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)\\&=ab.\end{aligned}}$

$\Box$

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.

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

${}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 Lemma von Euklid, das eine wichtige Eigenschaft einer Primzahl beschreibt.

Satz

Es sei ${}p$ eine Primzahl und ${}p$ teile ein Produkt ${}ab$ von natürlichen Zahlen ${}a,b\in \mathbb {N}$.

Dann teilt ${}p$ einen der Faktoren.

Beweis

Wir setzen voraus, dass ${}a$ kein Vielfaches von ${}p$ ist (andernfalls sind wir fertig). Dann müssen wir zeigen, dass ${}b$ ein Vielfaches von ${}p$ ist. Unter der gegebenen Voraussetzung sind ${}a$ und ${}p$ teilerfremd. Nach dem Lemma von Bezout gibt es ganze Zahlen ${}r,s$ mit

${}ra+sp=1\,$

Da ${}ab$ ein Vielfaches von ${}p$ ist, gibt es ein ${}t$ mit

${}ab=tp\,.$

Daher ist

${}b=b\cdot 1=b(ra+sp)=abr+bsp=tpr+bsp=p{\left(tr+bs\right)}\,.$

Also ist ${}b$ ein Vielfaches von ${}p$.

$\Box$

Aus dem Lemma von Euklid folgt sofort die etwas stärkere Aussage: Wenn eine Primzahl ${}p$ ein beliebiges Produkt ${}a_{1}a_{2}{\cdots }a_{n}$ teilt, dann teilt ${}p$ mindestens einen Faktor. Man wendet das Lemma einfach auf ${}(a_{1}a_{2}{\cdots }a_{n-1})\cdot a_{n}$ an (formal ist das eine Induktion über die Anzahl der Faktoren). Dies wird im Beweis des folgenden Hauptsatzes der elementaren Zahlentheorie verwendet.

Satz

Jede natürliche Zahl ${}n\in \mathbb {N}$, ${}n\geq 2$, besitzt eine eindeutige Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

${}n=p_{1}{\cdots }p_{r}\,$

mit Primzahlen ${}p_{i}$, und dabei sind die Primfaktoren bis auf ihre Reihenfolge eindeutig bestimmt.

Beweis

Die Existenz der Primfaktorzerlegung wurde bereits in Satz 12.9 gezeigt. Die Eindeutigkeit wird durch Induktion über ${}n$ gezeigt. Für ${}n=2$ liegt eine Primzahl vor. Sei nun ${}n\geq 3$ und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

${}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 ${}p_{1}=q_{1}$ sein muss. Daraus ergibt sich durch Kürzen, dass

${}p_{2}{\cdots }p_{r}=q_{2}{\cdots }q_{s}\,$

ist. Nennen wir diese Zahl ${}n'$. Da ${}n'<n$ ist, können wir die Induktionsvoraussetzung auf ${}n'$ anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen. 

$\Box$

In der kanonischen Primfaktorzerlegung schreibt man die beteiligten Primzahlen in aufsteigender Reihenfolge mit ihrem jeweiligen Exponenten, also beispielsweise

${}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.

Definition Referenznummer erstellen

Zu einer ganzen Zahl ${}n\neq 0$ und einer Primzahl ${}p$ nennt man den Exponenten, mit dem ${}p$ in der Primfaktorzerlegung von ${}n$ vorkommt, den Exponenten von ${}n$. Er wird mit ${}\nu _{p}(n)$ bezeichnet.

Statt Exponent spricht man auch von der Vielfachheit oder der Ordnung von ${}p$ in ${}n$. Wenn ${}p$ in der Primfaktorzerlegung nicht vorkommt, so ist

${}\nu _{p}(n)=0\,.$

Die Primfaktorzerlegung einer ganzen Zahl ${}n\neq 0$ kann man damit abstrakt und kompakt als

${}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 ${}n=14000$ ist die Primfaktorzerlegung gleich

${}14000=2^{4}\cdot 5^{3}\cdot 7\,$

und somit gilt

${}\nu _{2}(14000)=4\,,$

${}\nu _{5}(14000)=3\,,$

${}\nu _{7}(14000)=1\,$

und

${}\nu _{p}(14000)=0\,$

für alle weiteren Primzahlen ${}p$.

Lemma Referenznummer erstellen

Es sei ${}p$ eine Primzahl und

$\nu _{p}\colon \mathbb {Z} \setminus \{0\}\longrightarrow \mathbb {N} ,\,n\longmapsto \nu _{p}(n),$

der zugehörige ${}p$- Exponent. Dann gelten folgende Aussagen.

1. Die Zahl ${}p^{\nu _{p}(n)}$ ist die größte Potenz von ${}p$, die ${}n$ teilt.
2. Es ist

   ${}\nu _{p}(m\cdot n)=\nu _{p}(m)+\nu _{p}(n)\,.$

3. Es ist

   ${}\nu _{p}(m+n)=\operatorname {min} (\nu _{p}(m),\nu _{p}(n))\,$

   (es sei ${}m+n\neq 0$ vorausgesetzt).

Beweis

Siehe Aufgabe 21.14.

$\Box$

Korollar Korollar 21.7 ändern

Es seien ${}n$ und ${}k$ positive natürliche Zahlen. Dann wird ${}n$ von ${}k$ genau dann geteilt,

wenn für jede Primzahl ${}p$ die Beziehung

${}{\exp _{p}(n)}\geq {\exp _{p}(k)}\,$

gilt.

Beweis

${}(1)\Rightarrow (2)$. Aus der Beziehung ${}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 ${}t=\prod _{p}p^{{\exp _{p}(n)}-{\exp _{p}(k)}}$ eine natürliche Zahl mit ${}n=kt$.

$\Box$

Aus diesem Kriterium ergibt sich, dass man zu einer gegebenen Zahl, deren Primfaktorzerlegung vorliegt, einfach alle Teiler angeben kann. Bei

${}n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}\,$

sind die (positiven) Teiler genau die Zahlen

$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 ${}(r_{1}+1)(r_{2}+1)\cdots (r_{k}+1)$ Stück.

Korollar Referenznummer erstellen

Es seien ${}n$ und ${}m$ positive natürliche Zahlen mit den Primfaktorzerlegungen ${}n=\prod _{p}p^{\exp _{p}(n)}$ und ${}m=\prod _{p}p^{\exp _{p}(m)}$.

Dann ist

${}\operatorname {kgV} (n,m)=\prod _{p}p^{\max {\left({\exp _{p}(n)},{\exp _{p}(m)}\right)}}\,$

und

${}\operatorname {ggT} (n,m)=\prod _{p}p^{\min {\left({\exp _{p}(n)},{\exp _{p}(m)}\right)}}\,.$

Beweis

Dies folgt direkt aus Korollar 21.7.

$\Box$

Für die beiden Zahlen ${}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 ${}2^{2}\cdot 3^{2}\cdot 11$ und das kleinste gemeinsame Vielfache gleich ${}2^{3}\cdot 3^{3}\cdot 5\cdot 7^{2}\cdot 11$.