# Restklassenring/Z mod n/Multiplikative Ordnung und Divisionsalgorithmus/Textabschnitt

Es ist
    ${\frac {1}{7}}=0,{\overline {142857}}\,,$
die Periodenlänge ist also $6$. Zugleich besteht die Einheitengruppe von $\mathbb {Z} /(7)$ aus $6$ Elementen. Wir bringen hier generell den Divisionsalgorithmus (das schrifltiche dividieren) für die Berechnung der Dezimalentwicklung von $1$ durch $n$ mit dem Restklassenring $\mathbb {Z} /(n)$ in Verbindung. Insbesondere ergibt sich ein Zusammenhang zwischen der Periodenlänge der Dezimalentwicklung und der multiplikativen Ordnung der $10$ in $\mathbb {Z} /(n)$, falls $n$ teilerfrem zu $10$, also $10$ eine Einheit in $\mathbb {Z} /(n)$ ist. Der Divisionsalgorithmus zu $1$ durch $n$ funktioniert nach dem Schema (siehe Fakt und Fakt)
    $1=z_{0}\cdot n+r_{0}=0+1\,,$
    $10\cdot r_{0}=z_{-1}\cdot n+r_{-1}\,,$
    $10\cdot r_{-1}=z_{-2}\cdot n+r_{-2}\,,$
    $10\cdot r_{-2}=z_{-3}\cdot n+r_{-3}\,,...$
Es wird sukzessive Divisionen mit Rest durchgeführt, die $z_{-i}$ bezeichnen die $i$-te Nachkommaziffer des Bruches ${\frac {1}{n}}$ und der Rest $r_{-i}$ wird mit $10$ multipliziert, um die nächste Nachkommaziffer und den nächsen Rest zu erhalten. Wenn sich ein Rest wiederholt (und das muss passieren, da es ja nur endlich viele Reste gibt), so wiederholen sich ab dieser Stelle auch die Ziffern (die Ziffern können sich wiederholen, ohne dass daran schon das periodische Verhalten ablesbar ist) und man erhält eine Periodizität.

## Satz

Es sei $n$ eine positive natürliche Zahl mit der Faktorzerlegung
    $n=2^{r}\cdot 5^{s}\cdot d\,,$
wobei $d$ zu $n$ teilerfremd sei.
Dann ist die Periodenlänge der Dezimalentwicklung von ${\frac {1}{n}}$ gleich der multiplikativen Ordnung von $10$ in $\mathbb {Z} /(d)$.

### Beweis

Die Fälle $r,s=0$ oder $d=1$ sind erlaubt. Die Periodenlänge einer abbrechenden Dezimalentwicklung verstehen wir als $1$ (die $0$ wiederholt sich). Da die $10$ teilerfremd zu $d$ ist, ist $10$ in $\mathbb {Z} /(d)$ eine Einheit und besitzt daher eine multiplikative Ordnung. Der Divisionsalgorithmus berechnet sukzessive die Reste von $10^{i}$ in $\mathbb {Z} /(n)$, da ja der vorhergehende Rest mit $10$ multipliziert wird. Periode tritt ein, wenn sich Reste erstmalig wiederholen, wenn also $10^{i}=10^{j}$ in $\mathbb {Z} /(n)$ mit $i<j$ ist und $i,j$ minimal mit dieser Eigenschaft sind. Der chinesische Restsatz liefert die Isomorphie
    $\mathbb {Z} /(n)=\mathbb {Z} /(2^{r})\times \mathbb {Z} /(5^{s})\times \mathbb {Z} /(d)\,,$
und die Bedingung $10^{i}=10^{j}$ muss in den drei Komponenten gelten. In den ersten beiden Komponenten ist $10$ nilpotent, da ja $10^{r}$ ein Vielfaches von $2^{r}$ und $10^{s}$ ein Vielfaches von $5^{s}$ ist. Diese Komponenten sind also für die Periodenlänge unerheblich (allerdings spielen sie eine Rolle für die Frage, wann frühestens die Periodizität anfängt). In der dritten Komponente ist $10$ eine Einheit, also ein Element der Einheitengruppe ${\left(\mathbb {Z} /(d)\right)}^{\times }$. Nach Fakt tritt die erste Wiederholung ein, wenn erstmalig $10^{j}=10^{0}=1$ gilt, also bei der multiplikativen Ordnung von $10$.
$\Box$
Dass die Dezimalentwicklung von ${\frac {1}{7}}$ die Periode $6$ besitzt hängt unmittelbar damit zusammen, dass $10=3$ in $\mathbb {Z} /(7)$ ein Erzeuger der Einheitengruppe ist. Es ist
    ${\frac {1}{11}}=0,{\overline {09}}\,,$
die Periodenlänge $2$ ist die multiplikative Ordnung von $10=-1$ in $\mathbb {Z} /(11)$. Die Berechnung der multiplikativen Ordnung von $10$ in $\mathbb {Z} /(d)$ vereinfacht sich, wenn man für $d$ die Faktorzerlegung in zueinander teilerfremde Faktoren kennt.