Teilbarkeitstheorie (Z)/Teilen und GgT/Textabschnitt

Definition

Man sagt, dass die ganze Zahl ${}a$ die ganze Zahl ${}b$ teilt (oder dass ${}b$ von ${}a$ geteilt wird, oder dass ${}b$ ein Vielfaches von ${}a$ ist), wenn es eine ganze Zahl ${}c$ derart gibt, dass ${}b=c\cdot a$ ist. Man schreibt dafür auch ${}a{|}b$.

Lemma

In ${}\mathbb {Z}$ gelten folgende Teilbarkeitsbeziehungen.

1. Für jede ganze Zahl ${}a$ gilt ${}1\,{|}\,a$ und ${}a\,{|}\,a$.
2. Für jede ganze Zahl ${}a$ gilt ${}a\,{|}\,0$.
3. Gilt ${}a\,{|}\,b$ und ${}b\,{|}\,c$, so gilt auch ${}a\,{|}\,c$.
4. Gilt ${}a\,{|}\,b$ und ${}c\,{|}\,d$, so gilt auch ${}ac\,{|}\,bd$.
5. Gilt ${}a\,{|}\,b$, so gilt auch ${}ac\,{|}\,bc$ für jede ganze Zahl ${}c$.
6. Gilt ${}a\,{|}\,b$ und ${}a\,{|}\,c$, so gilt auch ${}a\,{|}\,{\left(rb+sc\right)}$ für beliebige ganze Zahlen ${}r,s$.

Beweis

Siehe Aufgabe.

$\Box$

Definition

Es seien ${}a_{1},\ldots ,a_{k}$ ganze Zahlen. Dann heißt eine ganze Zahl ${}t$ gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$, wenn ${}t$ jedes ${}a_{i}$ teilt (${}i=1,\ldots ,k$).

Eine ganze Zahl ${}g$ heißt größter gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$, wenn ${}g$ ein gemeinsamer Teiler ist und wenn jeder gemeinsame Teiler ${}t$ dieses ${}g$ teilt.

Die Elemente ${}a_{1},\ldots ,a_{k}$ heißen teilerfremd, wenn ${}1$ ihr größter gemeinsamer Teiler ist.

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$

Satz

Jede Menge von ganzen Zahlen ${}a_{1},\ldots ,a_{n}$

besitzt einen größten gemeinsamen Teiler ${}d$, und dieser lässt sich als Linearkombination der ${}a_{1},\ldots ,a_{n}$ darstellen, d.h. es gibt ganze Zahlen ${}r_{1},\ldots ,r_{n}$ mit

${}r_{1}a_{1}+r_{2}a_{2}+\cdots +r_{n}a_{n}=d\,.$

Insbesondere gibt es zu teilerfremden ganzen Zahlen ${}a_{1},\ldots ,a_{n}$ eine Darstellung der ${}1$.

Beweis

Dies folgt direkt aus Fakt und Fakt.

$\Box$

Man beachte, dass ein größter gemeinsamer Teiler, der nach dem Lemma von Bézout existiert, nicht eindeutig bestimmt ist. Denn ebenso ist mit ${}g$ auch das Negative ${}-g$ ein größter gemeinsamer Teiler. Häufig wählt man den Vertreter ${}\geq 0$, um Eindeutigkeit zu erreichen.