# Ganze Zahlen/Untergruppen/Einführung/Textabschnitt

Die Division mit Rest, die wir bisher nur für natürliche Zahlen formuliert haben, überträgt sich unmittelbar auf ganze Zahlen (der Divisor bleibt eine natürliche Zahl).

## Satz

Es sei $d$ eine fixierte positive natürliche Zahl.
Dann gibt es zu jeder ganzen Zahl $n$ eine eindeutig bestimmte ganze Zahl $q$ und eine eindeutig bestimmte natürliche Zahl $r$, $0\leq r\leq d-1$, mit

### Beweis

$\Box$

## Definition

Es sei $(G,e,\circ )$ eine Gruppe. Eine Teilmenge $H\subseteq G$ heißt Untergruppe von $G$ wenn folgendes gilt.
* $e\in H$.
* Mit $g,h\in H$ ist auch $g\circ h\in H$.
* Mit $g\in H$ ist auch $g^{-1}\in H$.
In einer Untergruppe kann man also die Verknüpfung der Gruppe ausführen, man kann das Inverse nehmen und das neutrale Element gehört dazu. In additiver Schreibweise, die für uns im Mittelpunkt steht, bedeuten die Bedingungen einfach
* $0\in H$.
* Mit $g,h\in H$ ist auch $g+h\in H$.
* Mit $g\in H$ ist auch das Negative $-g\in H$.
Beispielsweise bilden alle Vielfachen der $5$ innerhalb der ganzen Zahlen eine Untergruppe, die wir mit $\mathbb {Z} 5$ bezeichnen. Es ist ja
    $0=0\cdot 5\,,$
wenn $g=5\cdot a$ und $h=5\cdot b$ sind, so ist
    $h+g=5\cdot (a+b)\,$
nach dem Distributivgesetz und mit $g=5\cdot a$ ist $-g=5\cdot (-a)$. Wie im eingangs gegebenen Beispiel kann man sich eine Menge $a_{1},\ldots ,a_{k}$ von ganzen Zahlen (Eimergrößen) vorgeben und sich fragen, welche Zahlen man daraus mit Hilfe von ganzzahligen Koeffizienten bilden kann (welche Wassermengen man transportieren kann). Es geht also um die Menge aller Zahlen der Form
    $n_{1}a_{1}+\cdots +n_{k}a_{k}{\text{ mit }}n_{j}\in \mathbb {Z} .$
Diese Gesamtmenge bildet eine Untergruppe von $\mathbb {Z}$, siehe Aufgabe, man spricht von der von den $a_{1},\ldots ,a_{k}$ erzeugten Untergruppe von $\mathbb {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 „Ein-Eimer-Satz“.

## Satz

Die Untergruppen von $\mathbb {Z}$ sind genau
die Teilmengen der Form
mit einer eindeutig bestimmten nichtnegativen Zahl $d$.

### Beweis

Eine Teilmenge der Form $\mathbb {Z} d$ ist aufgrund des Distributivgesetzes eine Untergruppe. Es sei umgekehrt $H\subseteq \mathbb {Z}$ eine Untergruppe. Bei $H=0$ kann man $d=0$ nehmen, sodass 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 $H=\mathbb {Z} d$. Dabei ist die Inklusion $\mathbb {Z} d\subseteq H$ klar, da mit $d$ alle (positiven und negativen) Vielfachen von $d$ dazugehören müssen. Für die umgekehrte Inklusion sei $h\in H$ beliebig. Nach der Division mit Rest gilt
    $h=qd+r{\text{ mit }}0\leq r<d.$
Wegen $h\in H$ und $qd\in H$ ist auch $r=h-qd\in H$. Nach der Wahl von $d$ muss wegen $r<d$ gelten: $r=0$. Dies bedeutet $h=qd$ und damit $h\in \mathbb {Z} d$, also $H\subseteq \mathbb {Z} d$.
$\Box$

## Lemma

Es seien $a_{1},\ldots ,a_{k}$ ganze Zahlen und $H=(a_{1},\ldots ,a_{k})={\left\{n_{1}a_{1}+n_{2}a_{2}+\cdots +n_{k}a_{k}\mid n_{j}\in \mathbb {Z} \right\}}$ die davon erzeugte Untergruppe.
Eine ganze Zahl $t$ ist ein gemeinsamer Teiler der $a_{1},\ldots ,a_{k}$ genau dann, wenn $H\subseteq \mathbb {Z} t$ ist, und $t$ ist ein größter gemeinsamer Teiler genau dann, wenn $H=\mathbb {Z} t$ ist.

### Beweis

Aus $H=(a_{1},\ldots ,a_{k})\subseteq (t)$ folgt sofort $a_{i}\mathbb {Z} \subseteq t\mathbb {Z}$ für jedes $i=1,\ldots ,k$, was gerade bedeutet, dass $t$ diese Zahlen teilt, also ein gemeinsamer Teiler ist. Es sei umgekehrt $t$ ein gemeinsamer Teiler. Dann ist $a_{i}\in t\mathbb {Z}$ und da $H=(a_{1},\ldots ,a_{k})$ die kleinste Untergruppe ist, die alle $a_{i}$ enthält, muss $H\subseteq t\mathbb {Z}$ gelten.
Aufgrund von Fakt wissen wir, dass es eine ganze Zahl $g$ gibt mit $H=\mathbb {Z} d$. Für einen anderen gemeinsamen Teiler $t$ der $a_{i}$ gilt $\mathbb {Z} d=H\subseteq \mathbb {Z} t$, sodass $d$ von allen anderen gemeinsamen Teilern geteilt wird, also ein größter gemeinsamer Teiler ist.
$\Box$