# Divisionsalgorithmus/Ziffernfolge/Einführung/Textabschnitt
## Verfahren

Es seien $a,b$ natürliche Zahlen mit $b$ positiv. Beim Divisionsalgorithmus $a:b$ führt man sukzessive die (unendlich vielen) Divisionen mit Rest
    $a=z_{0}\cdot b+r_{0}\,,$
    $10\cdot r_{0}=z_{-1}\cdot b+r_{-1}\,,$
    $10\cdot r_{-1}=z_{-2}\cdot b+r_{-2}\,,$
    $10\cdot r_{-2}=z_{-3}\cdot b+r_{-3}\,,...$
aus, d.h. man berechnet rekursiv aus $r_{-i}$ mittels
    $10\cdot r_{-i}=z_{-i-1}\cdot b+r_{-i-1}\,$
die $z_{-i-1}$ und die $r_{-i-1}$. Die Folge $z_{-i}$, $i\in \mathbb {N}$, heißt die Ziffernfolge und die Folge $r_{-i}$, $i\in \mathbb {N}$, heißt die Restefolge des Divisionsalgorithmus.
Man schaut also, wie oft $b$ in $a$ hineinpasst (das ergibt $z_{0}$, den ganzzahligen Anteil der Division) und welcher Rest dabei übrigbleibt. Dann schaut man, wie oft $b$ in das Zehnfache dieses Restes hineinpasst (das ergibt $z_{-1}$, die erste Nachkommaziffer der Division) und welcher Rest dabei übrigbleibt, und wiederholt diesen Rechenschritt unendlich oft. Dieses Verfahren ist aus der Schule bekannt. Als Ergebnis wird die „unendliche Kommazahl“
    $z,z_{-1}z_{-2}z_{-3}\ldots$
notiert, wobei die ganze Zahl $z$ selbst in ihrer Dezimalentwicklung genommen wird. Unklar ist dabei, welchen genauen Sinn ein solcher Ausdruck besitzt. Dies lässt sich im Rahmen der Konvergenz von Folgen befriedigend präzisieren. Die Indizierung ist hier so gewählt, dass sich die Ziffer $z_{-i}$ (für $i\geq 1$) auf $10^{-i}$ bezieht. D.h. $z_{-i}$ ist die $i$-te Nachkommaziffer des Ergebnisses der Division.

## Lemma

Es seien $a,b$ natürliche Zahlen mit $b$ positiv und es seien $z_{-i}$, $i\in \mathbb {N}$, und $r_{-i}$, $i\in \mathbb {N}$, die im Divisionsalgorithmus berechneten Folgen. Dann gelten folgende Eigenschaften.

### Beweis

* Ist eine Eigenschaft der Division mit Rest.
* Wegen ist Bei der Division von $10\cdot r_{-i}=z_{-i-1}\cdot b+r_{-i-1}$ durch $b$ ist somit der ganzzahlige Anteil $z_{-i-1}$ echt kleiner als $10$.
    $r_{-i}\leq b-1\,$
    $10\cdot r_{-i}\leq 10\cdot (b-1)\,.$
* Dies folgt unmittelbar aus dem rekursiven Aufbau des Divisionsalgorithmus.
* Im Fall, dass für ein $k$ der Rest $r_{-k}=0$ ist, ergibt sich dies unmittelbar aus (3), wobei man $\ell =1$ wählen kann. Nehmen wir also an, dass alle $r_{-i}$ von $0$ verschieden sind. Da die Reste allesamt zwischen $1$ und $b-1$ liegen, muss es in ihnen irgendwann eine Wiederholung geben, sagen wir, dass gilt. Da $z_{-i-1}$ und $r_{-i-1}$ allein von $r_{-i}$ abhängt, wiederholt sich dann die Restfolge und die Ziffernfolge unendlich oft periodisch.
    $r_{-1},r_{-2},r_{-3}$
    $r_{-k-\ell }=r_{-k}\,$
    $r_{-k},r_{k-1},\ldots ,r_{-k-\ell +1}\,\,{\text{ bzw. }}\,\,z_{-k},z_{k-1},\ldots ,z_{-k-\ell +1}$
* Aus der Division mit Rest ergibt sich direkt die entsprechende Division mit Rest woraus die Behauptung folgt.
    $10\cdot r_{-i}=z_{-i-1}\cdot b+r_{-i-1}\,$
    $10\cdot {\left(m\cdot r_{-i}\right)}=z_{-i-1}\cdot {\left(m\cdot b\right)}+{\left(m\cdot r_{-i-1}\right)}\,,$
* Der Divisionsalgorithmus ist in diesem Fall u.s.w., woraus die Aussagen ablesbar sind.
    $\sum _{j=0}^{t}c_{j}10^{j}={\left(\sum _{j=s}^{t}c_{j}10^{j-s}\right)}10^{s}+\sum _{j=0}^{s-1}c_{j}10^{j}\,,$
    $10\cdot {\left(\sum _{j=0}^{s-1}c_{j}10^{j}\right)}=c_{s-1}10^{s}+10\cdot {\left(\sum _{j=0}^{s-2}c_{j}10^{j}\right)}\,,$
    $10^{2}\cdot {\left(\sum _{j=0}^{s-2}c_{j}10^{j}\right)}=c_{s-2}10^{s}+10^{2}\cdot {\left(\sum _{j=0}^{s-3}c_{j}10^{j}\right)}\,,$
* Wenn ein Dezimalbruch vorliegt, so können wir wegen (5) annehmen, dass eine Zehnerpotenz ist. Dann folgt die Aussage mit der abbrechenden Ziffernfolge aus (6). Wenn ein $r_{-k}=0$, so sind nach (3) alle folgenden Ziffern gleich $0$. Wenn umgekehrt $z_{-i}=0$ für alle $i\geq k$ gilt, so wird die Rekursionsbedingung für $i\geq k$ zu Nehmen wir $z_{-k}\neq 0$ an. Dann ist u.s.w., was zu einem Widerspruch führt, da nach Fakt die Zehnerpotenzen schließlich die Zahl $b$ überschreiten. Wenn ein $r_{-k}=0$ ist, so folgt rekursiv aus bzw. dass die Brüche Dezimalbrüche sind. Somit ist auch ${\frac {a}{b}}$ ein Dezimalbruch.
    $b=10^{s}\,$
    $10\cdot r_{-i}=r_{-i-1}\,.$
    $r_{-k-1}=10r_{-k}\,,$
    $r_{-k-3}=10r_{-k-1}=10^{2}r_{-k}\,,$
    $10r_{-i}=z_{-i-1}\cdot b+r_{-i-1}\,$
    ${\frac {r_{-i}}{b}}={\frac {z_{-i-1}}{10}}+{\frac {r_{-i-1}}{10\cdot b}}\,,$
    ${\frac {r_{-k}}{b}}=0,\,{\frac {r_{-k+1}}{b}},\,{\frac {r_{-k+2}}{b}},\ldots ,{\frac {r_{-1}}{b}}\,,{\frac {r_{0}}{b}}$
$\Box$
Wir haben insbesondere bewiesen, dass beim Divisionsalgorithmus irgendwann eine Periodizität auftritt und gezeigt, wie diese zu finden ist. Das kleinste positve $\ell$, das die Eigenschaft aus (4) erfüllt, heißt die Periodenlänge der Division. Die Eigenschaft (6) bedeutet, dass die Ziffernfolge, die sich aus dem allgemeinen Divisionsalgorithmus im Falle der Division durch eine Zehnerpotenz ergibt, mit der endlichen Kommazahl aus Definition übereinstimmt. Das Ergebnis des Divisionsalgorithmus wird als
    $z_{0},z_{-1}z_{-2}\ldots z_{-k}{\overline {z_{-k-1}\ldots z_{-k-\ell }}}$
notiert, wobei die überstrichenen Zahlen die Periode darstellen.

## Bemerkung

Über die Periodenlänge kann man einige präzise Aussagen machen, die über Fakt (4) hinausgehen und die wir im Moment noch nicht beweisen können. Es seien $a$ und $b$ teilerfremd und $b$ sei auch teilerfremd zu $10$. Dann hängt die Periodenlänge $\ell$ der Division $a:b$ allein davon ab, welche minimale Zehnerpotenz $10^{k}$ mit $k\geq 1$ bei Division durch $b$ den Rest $1$ besitzt. Für den Fall $a=1$ siehe Aufgabe. Der minimale Exponent ist die Periodenlänge. Wenn $b=p$ eine Primzahl ist, so ist diese Periodenlänge ein Teiler von $p-1$. Wenn die Periodenlänge von $1:p$ genau $p-1$ ist, so gilt dies bei sämtlichen Divisionen $a:p$ mit $a$ teilerfremd zu $p$, und die Reihenfolge der Ziffern ist eine zyklische Vertauschung der Reihenfolge der Ziffern zu $1:p$. Siehe als Beispiel hierzu Aufgabe.