# Natürliche Zahlen/Teilbarkeit/Einführung/Textabschnitt
## Definition

Man sagt, dass die natürliche Zahl $a$ die natürliche Zahl $b$ teilt (oder dass $b$ von $a$ geteilt wird, oder dass $b$ ein Vielfaches von $a$ ist), wenn es eine natürliche Zahl $c$ derart gibt, dass $b=c\cdot a$ ist. Man schreibt dafür auch $a{|}b$.
Beispielsweise sind $1,2,5,10$ Teiler von $10$ und $1,3,9,27,81$ die Teiler von $81$. Eine Zerlegung
    $n=st\,$
nennt man auch eine Faktorzerlegung von $n$. Wenn $a$ ein Teiler von $b$ ist und
    $a\neq 0\,,$
so ist die Zahl $c$ mit $b=ac$ nach der Kürzungsregel eindeutig bestimmt. Man nennt diese Zahl den Gegenteiler oder komplementären Teiler und schreibt dafür ${\frac {b}{a}}$. Da wir im Moment die rationalen Zahlen noch nicht zur Verfügung haben, ist dies nur dann eine erlaubte Schreibweise, wenn die Teilerbeziehung vorliegt und $a\neq 0$ ist (so wie die Schreibweise $a-b$ bisher nur erlaubt ist, wenn $b\leq a$ ist). Es ist also $0$ ein Teiler der $0$, der Ausdruck $0/0$ ist aber nicht definiert. Wenn $a\neq 0$ ein Teiler von $b$ ist, so nennt man die Bestimmung des eindeutig bestimmten $c$ mit
    $b=ac\,$
Teilen. Man sagt, dass man $b$ durch $a$ teilt mit dem Ergebnis $c$.

## Lemma

Es sei $n\neq 0$ eine natürliche Zahl und $t$ ein Teiler von $n$.
Dann ist $t\leq n$.
Insbesondere besitzt $n$ nur endlich viele Teiler.

### Beweis

Da der Teiler $0$ ausgeschlossen ist, sind bei einer Faktorzerlegung $n=tc$ beide Faktoren $\geq 1$. Wegen Fakt (3) ist daher
    $n=tc\geq t\cdot 1=t\,.$
Der Zusatz ist klar, da es unterhalb von $n$ überhaupt nur endlich viele natürliche Zahlen gibt.
$\Box$
Wenn man also alle Teiler einer natürlichen Zahl $n$ finden möchte, so muss man einfach die Zahlen
    $a\leq n\,$
der Reihe nach durchgehen und ihre Vielfachen
    $1a=a,2a,3a,\ldots$
durchgehen, bis die Zahl $n$ auftaucht (in welchem Fall $a$ ein Teiler ist) oder eine Zahl $>n$ auftaucht (dann liegt kein Teiler vor). Übrigens muss man nicht die Zahlen bis $n$ durchprobieren, sondern lediglich bis zur ersten Zahl $r$ mit $r^{2}\geq n$ (man muss also nur bis zur Größenordnung der Quadratwurzel aus $n$ gehen). Dann muss man aber für jeden Teiler
    $t\leq r\,$
auch den Gegenteiler mitanführen, siehe Aufgabe. Für $105$ muss man maximal bis $11$ gehen. Es ergeben sich die Zerlegungen
    $105=1\cdot 105=3\cdot 35=5\cdot 21=7\cdot 15\,$
und die Teiler sind somit $1,3,5,7,15,21,35,105$.
Eine durch $2$ teilbare Zahl, also ein Vielfaches von $2$, heißt gerade, eine nicht durch $2$ teilbare Zahl heißt ungerade. Für einige Zahlen gibt es einfache Tests, ob sie ein Teiler einer gewissen Zahl sind, die allerdings auf dem Dezimalsystem beruhen. Eine weitere wichtige Möglichkeit ist die Division mit Rest. Auch der dritte Teil des folgenden Lemmas hilft: Wenn $a$ kein Teiler von $n$ ist, so sind sämtliche Vielfache von $a$ ebenfalls kein Teiler von $n$.

## Lemma

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

### Beweis

* Ist klar wegen
    $a=a\cdot 1\,.$
* Ist klar wegen
    $0=a\cdot 0\,.$
* Die beiden Voraussetzungen bedeuten die Existenz von $s,t\in \mathbb {N}$ mit $b=as$ und $c=bt$. Somit ist und $a$ ist auch ein Teiler von $c$.
    $c=bt=(as)t=a(st)\,$
* Aus den Voraussetzungen $b=as$ und $d=tc$ ergibt sich direkt also ist $ac$ ein Teiler von $bd$.
    $bd=astc=acts\,,$
* Aus der Voraussetzung $b=as$ ergibt sich direkt also ist $ac$ ein Teiler von $bc$.
    $bc=acs\,,$
* Aus den Voraussetzungen $b=at$ und $c=au$ ergibt sich direkt mit dem Distributivgesetz also ist $a$ ein Teiler von $rb+sc$.
    $rb+sc=rat+sau=a(rt+su)\,,$
$\Box$

## Beispiel

Wir betrachten die positiven natürlichen Zahlen $\mathbb {N} _{+}$ zusammen mit der Teilbarkeitsbeziehung. Dies ergibt eine Ordnung auf $\mathbb {N} _{+}$. Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets $n{|}n$ ist, wie $m=1$ zeigt. Die Transitivität wurde in Fakt (3) gezeigt. Die Antisymmetrie folgt so: Aus $n=ak$ und $k=bn$ folgt $n=(ab)n$. Da wir uns auf positive natürliche Zahlen beschränken, folgt mit der Kürzungsregel $ab=1$ und daraus wegen $a,b\leq ab$ auch $a=b=1$. Also ist $k=n$. Einfache Beispiele wie $2$ und $3$ zeigen, dass hier keine totale Ordnung vorliegt, da weder $2$ von $3$ noch umgekehrt geteilt wird.