# Ganze Zahlen/KgV und GgT/Untergruppen/Einführung/Textabschnitt

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

Es seien $a_{1},\ldots ,a_{k}$ ganze Zahlen.
Dann ist
wobei $u$ das kleinste gemeinsame Vielfache der $a_{1},\ldots ,a_{k}$ ist.

### Beweis

Nach Aufgabe ist der Durchschnitt der Untergruppen $\mathbb {Z} a_{i}$ wieder eine Untergruppe von $\mathbb {Z}$. Nach Fakt 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

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

### Beweis

* 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 Fakt gibt es im teilerfremden Fall Zahlen $r,s\in \mathbb {Z}$ mit $ra+sb=1$. Daher ist ein Vielfaches von $ab$.
    $f=f\cdot 1=f(ra+sb)=fra+fsb=vbra+uasb=(vr+us)ab\,$
* 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.
* 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.
* 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.