# Division mit Rest/Z/Ohne Beweis/Untergruppen/Textabschnitt

Zu einer ganzen Zahl $d$ ist die Menge
    $\mathbb {Z} d={\left\{kd\mid k\in \mathbb {Z} \right\}}\,$
aller Vielfachen von $d$ eine Untergruppe von $\mathbb {Z}$. Wir wollen zeigen, dass jede Untergruppe der ganzen Zahlen $\mathbb {Z}$ diese Gestalt besitzt, also von einem Element erzeugt wird.

## 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

Zur Existenz. Bei $n=0$ ist $q=r=0$ eine Lösung. Es sei $n$ positiv. Da $d$ positiv ist, gibt es ein Vielfaches $ad\geq n$. Daher gibt es auch eine Zahl $q$ mit $qd\leq n$ und $(q+1)d>n$. Es sei $r:=n-qd$. Dann ist
    $qd\leq qd+r<qd+d\,$
und daher ist $0\leq r<d$ wie gewünscht. Bei $n$ negativ kann man schreiben $-n={\tilde {q}}d+{\tilde {r}}$ nach dem Resultat für positive Zahlen. Daraus ergibt sich
    $n=(-{\tilde {q}})d-{\tilde {r}}={\begin{cases}(-{\tilde {q}})d+0{\text{ bei }}{\tilde {r}}=0\\(-{\tilde {q}}-1)d+d-{\tilde {r}}{\text{ sonst}}\,.\end{cases}}$
Im zweiten Fall erfüllen $q=-{\tilde {q}}-1$ und $r=d-{\tilde {r}}$ die Bedingungen. Zur Eindeutigkeit. Es sei $qd+r=n={\tilde {q}}d+{\tilde {r}}$, wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung ${\tilde {r}}\geq r$. Dann gilt $(q-{\tilde {q}})d={\tilde {r}}-r$. Diese Differenz ist nichtnegativ und kleiner als $d$, links steht aber ein Vielfaches von $d$, sodass die Differenz $0$ sein muss und die beiden Darstellungen überein stimmen.
$\Box$
In der Notation des vorstehenden Satzes soll $q$ an Quotient und $r$ an Rest erinnern. Die Division mit Rest kann man auch so verstehen, dass man jede rationale Zahl $n/d$ als
    ${\frac {n}{d}}=\lfloor {\frac {n}{d}}\rfloor +{\frac {r}{d}}\,$
schreiben kann, wobei $\lfloor s\rfloor$ die größte ganze Zahl $\leq s$ bedeutet und der rationale Rest $r/d$ die Bedingungen $0\leq r/d<1$ erfüllt. In dieser Form kann man auch eine Division mit Rest für jede reelle Zahl aus den Axiomen der reellen Zahlen beweisen.

## 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$