Matheseiten-Übersicht
zurück

Berechnung der Periodenlänge von Dezimalbrüchen

Beim Dividieren zweier Zahlen mit dem Taschenrechner oder auf dem Papier erhält man bekanntlicherweise immer dann Kommastellen, wenn sich der Dividend nicht ohne Rest durch den Divisor teilen läßt. Manchmal gibt es nur „wenige“ Kommastellen, besser gesagt: eine begrenzte Zahl von Kommastellen, oftmals aber unendlich viele, die jedoch immer aus einer periodischen Wiederholung derselben Zahlenfolge bestehen. Man weiß vom schriftlichen Dividieren: Sobald sich („hinter dem Komma“) ein Rest wiederholt, wiederholen sich ab da auch alle anderen Reste, und dieses Spielchen geht bis in alle Ewigkeit weiter. Entweder bricht der Dezimalbruch ab, nämlich wenn ein Rest 0 auftritt, oder er ist periodisch. Warum das so ist, und wie lange diese Zahlenfolge (die „Periode“) ist, wird auf dieser Seite beschrieben.

Warum ist ein nichtabbrechender Dezimalbruch automatisch periodisch?

Bekanntlicherweise kann man die Kommastellen eines Dezimalbruchs durch das aus der Grundschule bekannte Verfahren des schriftlichen Dividierens mit Resten erhalten. Sobald der Rest 0 auftaucht, ist man fertig, sobald ein anderer Rest wiederholt auftritt, entsteht zwangsläufig eine Periode. (Vorausgesetzt, man hat bei beiden Stellen nur Nullen zum Herunterholen - aber das ist immer so, weil der Dividend (Zähler) ja eine ganze Zahl ist und „hinter dem Komma“ nichts als Nullen bietet.)

Solange sich kein Rest wiederholt, müssen logischerweise alle Reste unterschiedlich sein. Kann es nun beliebig viele verschiedene Reste geben? Natürlich nicht, denn die Reste sind immer kleiner als der Divisor (Nenner des Bruchs). Weil die Null als Rest hier nicht in Frage kommt (sonst keine Periode), bleiben die Reste 1, 2, 3, 4 bis „Nenner minus 1“, also „Nenner minus 1“ verschiedene Reste. Daraus folgt: Die Periode eines Bruchs mit dem Nenner n kann höchstens n-1 Stellen haben, denn spätestens beim n-ten Rest muß sich ein bereits dagewesener Rest wiederholen.

Als nächstes überlegen wir, von was es abhängt, ob überhaupt eine Periode bzw. wann keine Periode entsteht.

Wann entsteht keine Periode

Da wir im Dezimalsystem rechnen, entspricht jede Ziffer von Dezimalzahlen einer Potenz von 10: Einerstelle, Zehnerstelle, Hunderterstelle usw. sind die Stellen vor dem Komma (links vom Komma), Zehntelstelle, Hundertstelstelle, Tausendstelstelle die nach dem Komma. Die Zahl 0,3729 kann man daher in Brüchen so schreiben:

               3    7      2      9        3000 + 700 + 20 + 9        3729
   0,3729  =  —— + ——— + ———— + —————  =  —————————————————————  =  ———————
              10   100   1000   10000              10000             10000

Wenn man eine natürliche Zahl durch Potenzen von 10 teilt, entsteht also keine Periode.
Auf Brüche übertragen: Alle Brüche, deren Nenner eine Potenz von 10 (1, 10, 100, 1000, ...) ist, haben keine Periode.

Das sind aber längst nicht alle Brüche ohne Periode: Wenn man z.B. durch 2, durch 4, durch 5 oder durch 8 teilt, entstehen auch keine periodische Dezimalbrüche (1/2=0,5 ; 1/4=0,25 ; 1/5=0,2 und 1/8=0,125). Das Spezielle an diesen Divisoren bzw. Nennern ist, daß man sie immer auf Potenzen von 10 erweitern kann:

    1    5            1    25             1    2             1    125
    — = ——            — = ———             — = ——             — = ————
    2   10            4   100             5   10             8   1000

Nur wenn es gelingt, den Bruch so zu erweitern, daß der Nenner eine Zehnerpotenz ist, kann er als nichtperiodischer Dezimalbruch geschrieben werden.

Welche Nenner lassen sich so erweitern? Offensichtlich alle, die Teiler irgendeiner Zehnerpotenz sind. - Zehnerpotenzen lassen sich immer nur durch 2 und 5 teilen (denn 10=2·5, 100=10·10=2·5·2·5 usw.); und daher lassen sich nur diejenigen Nenner auf Zehnerpotenzen erweitern, die selbst nur durch 2 und/oder 5 teilbar sind. Wenn sich ein Bruch nicht derartig erweitern läßt, dann kann er auch nicht in eine abbrechende Dezimaldarstellung gebracht werden und muß daher eine nichtabbrechende Dezimaldarstellung besitzen.

Nur Brüche, deren Nenner (im vollständig gekürzten Zustand) keine anderen Primfaktoren als 2en und/oder 5en besitzen, ergeben einen unperiodischen Dezimalbruch, der eine endliche Zahl an Kommastellen besitzt.

 

Wieviele Kommastellen haben unperiodische Dezimalbrüche?

Um diese Frage beantworten zu können, überlegen wir zunächst, mit welcher Zahl ein geeigneter Bruch erweitert werden muß, damit sein Nenner zu einer Zehnerpotenz wird.

Bei Zehnerpotenzen kommen in der Primfaktorzerlegung immer gleich viele 2en und 5en vor, denn bei der 10 selbst kommen ja auch gleich viele 2en und 5en vor, nämlich je eine: 10 = 2·5. Beim Multiplizieren mit 10 erhöhen sich die Anzahlen an 2en und 5en immer gleich. Man muß den Bruch also so erweitern, daß der Unterschied zwischen der Anzahl der 2en und der 5en in der Primfaktorzerlegung des Nenners ausgeglichen wird.

Bsp: 160 = 2·2·2·2·2·5 hat vier 5en weniger als 2en, muß also mit 54=625 erweitert werden:

     1         1             5·5·5·5               625           625
    ——— = ——————————— = ——————————————————— = —————————————— = —————— = 0,00625
    160   2·2·2·2·2·5   2·2·2·2·2·5·5·5·5·5   10·10·10·10·10   100000

 

0,00625 hat fünf Kommastellen, denn der Nenner im letzten Bruch ist 105=100000. Wir kamen auf fünf 10en durch die fünf 2en in der Primfaktorzerlegung der 160. Die Zahl der Zehnen wurde also bestimmt durch die Zahl der 2en, denn die kleinere Anzahl der 5en mußte auf die größere Anzahl der 2en erweitert werden. Allgemein gesagt bestimmt die größere Anzahl an 2en oder 5en die Anzahl der 10en im erweiterten Nenner und damit die Anzahl der Dezimalstellen nach dem Komma.

Die Zahl der unperiodischen Kommastellen wird gegeben durch die maximale Anzahl von 2en oder 5en in der Primfaktorzerlegung des Nenners

Falls der Nenner nicht ausschließlich aus 2en und 5en „besteht“, dann bricht der Dezimalbruch nicht ab, denn dann läßt er sich nicht auf eine Zehnerpotenz erweitern. Er muß dann automatisch periodisch sein (siehe oben).

Man kann übrigens auch solche Nenner so erweitern, daß die Zahl der 2en und 5en ausgeglichen wird. Bsp.:

     1        1            25            25       25  
    ——— = ————————— = ————————————— = ———————— = ————
    280   2·2·2·5·7   2·2·2·5·5·5·7   1000 · 7   7000

Wegen 25:7 = 3 Rest 4 kann man 25/7000 auch so schreiben:

     25      3      4           
    ———— = ———— + ————          (Wenn man die beiden Brüche addiert, ist 7000 der Hauptnenner,
    7000   1000   7000           d.h. der Zähler der Summe ergibt sich aus 7·3 + 4 = 25)

Da 4/7000 < 1/1000, fängt die Periode sicher erst nach der 4. Kommastelle an, und der Anfang des Dezimalbruchs wird gegeben durch 3/1000 = 0,003.

Weil sich die 4 im obigen Beispiel als Rest bei der Division durch 7 ergab und somit allgemein immer kleiner ist als der jeweilige Divisor, läßt sich diese Feststellung verallgemeinern, wodurch der oben eingerahmte Satz über die Länge des unperiodischen Teils eines Dezimalbruchs auch für periodische Brüche gilt. Läßt sich ein Nenner weder durch 2 noch durch 5 teilen, so beginnt die Periode des zugehörigen Dezimalbruchs folglich direkt nach dem Komma.

 

Die Länge der Periode

Die Länge der Periode hängt offensichtlich nur von der Zahl ab, die übrigbleibt, wenn man aus dem Nenner alle 2en und 5en herauskürzt. (Vergleiche das Beispiel 1/280 oben.) Im folgenden können wir uns also auf Nenner beschränken, die nicht durch 2 oder 5 (und damit auch nicht durch 10) teilbar sind.

Die Dezimalstellen erhält man bekanntlicherweise durch schriftliche Division. Wenn sich bei der schriftlichen Division ein Rest („nach dem Komma“) wiederholt, wiederholen sich ab da alle Reste, und die Periode ist gefunden.

Die Frage ist also, wieviele verschiedene Reste bei der Division durch eine bestimmte Zahl entstehen.

Weil die Reste bei der Division durch die Zahl m immer kleiner als m sind, kann es einschließlich der 0 höchstens m verschiedene Reste geben. Die 0 selbst kommt auch nicht in Frage, denn wenn ein Rest 0 auftritt, ist der Bruch ja nicht periodisch. Damit ist die Anzahl der möglichen verschiedenen Reste höchstens m-1.

Um die Sache etwas zu vereinfachen, beschränken wir uns auf den Dividenden 1, d.h. auf die Frage, wie lange die Periode von 1:m ist. (Später wird sich noch herausstellen, daß die Periodenlänge vom Zähler unabhängig ist, soweit Zähler und Nenner keine gemeinsamen Teiler besitzen.)

Als Beispiel betrachten wir den Bruch 1/13 und dividieren dazu schriftlich 1 durch 13:

             ——————
  1 : 13 = 0,076923   
 -0
  —
  10        
  -0
  ——
  100
  -91
  ———
    90
   -78
    ——
    120
   -117
    ———
      30
     -26
      ——
       40
      -39
       ——
        1

Der erste Rest, der sich wiederholt, ist die 1. Dies passiert im 6. Schritt, womit die Periodenlänge 6 ist. Weil der Dividend 1 kleiner als der Divisor 13 ist, muß der erste Rest gleich dem Dividenden 1 sein. Das gilt allgemein für alle Brüche 1/m mit m>1. Daher ist die Periode gefunden, wenn der Rest 1 zum zweiten Mal auftritt.

Das vereinfacht die Angelegenheit ein wenig, da man nicht immer alle bisherigen Reste durchsehen muß. Allerdings liegt die Hauptarbeit im Dividieren und Berechnen der Reste. Es gibt glücklicherweise auch hier eine Möglichkeit der Vereinfachung!

Um dem auf die Schliche zu kommen, schauen wir uns mal an, wie die Reste eigentlich zustande kommen. Die 1 ergab sich aus 1-0. Die 10 aus 10-0. Irgendwie uninteressant. Vielleicht ist nur zu bemerken, daß die „erste“ 10 durch Anhängen einer Null an die 1 entstanden ist, was einer Multiplikation mit 10 entspricht.
Interessanter wird es jetzt: Die 9 ergibt sich aus 100-91 = 100-7·13.
Die 91 ist ein Vielfaches der 13, die 100 entstand aus der 1 mit zwei heruntergeholten Nullen.

Weiter: Die 12 entsteht aus 90-78 = 90-6·13. Nun gut aufgepaßt!
- Die 90 entstand aus der 9 mit angehängter 0, d.h. aus 9·10.
- Die 12 ergibt sich somit insgesamt aus 9·10 - 6·13 = (100-7·13)·10 - 6·13
- (100-7·13)·10 - 6·13 = 1000 - 70·13 - 6·13 = 1000 - 76·13
- Damit ist die 12 der Rest bei der Division 1000:13!

Weiter: Der nächste Rest 3 entsteht aus 120-117 = 120-9·13
- 3 = 120 - 9·13 = 12·10 - 9·13 = (1000 - 76·13)·10 - 9·13 = 10000 - 760·13 - 9·13 = 10000 - 769·13
- 3 ist der Rest bei der Division 10000:13.

Offensichtlich sind die auftretenden Reste die Reste bei der Division der „zugehörigen“ Zehnerpotenz durch n.

Da wir nach dem zweiten Auftreten des Restes 1 suchen, müssen wir „nur“ überlegen, wann bei 10:m, 100:m, 1000:m, 10000:m usw. zum ersten Mal der Rest 1 auftritt.

Die Anzahl der periodischen Kommastellen beim Nenner m wird gegeben durch die kleinste Zahl n, bei der die Division von 10n durch m den Rest 1 ergibt.

Damit ist das Leben schon viel einfacher geworden, denn immerhin entfällt die mächtige Fehlerquelle, daß ein falsch berechneter Rest die ganze folgende Rechnung falsch macht. Zehnerpotenzen schreiben sich ohne Rechnung direkt hin, und mit Zehnerpotenzen läßt sich einigermaßen angenehm rechnen, wenngleich es wesentlich angenehmer wäre, durch sie zu teilen. (Siehe das Beispiel unten!)

Man kann sich das Rechnen aber noch weiter vereinfachen: Es geht uns ja nur um die Reste bei der Division; und deshalb schauen wir uns das Verhalten dieser Reste bei der Division von wachsenden Zehnerpotenzen durch m etwas genauer an. Zum besseren Verständnis wählen wir ein Zahlenbeispiel: m=7

1:7 = 0 Rest 1

10:7 = 1 Rest 3
   Der Rest 3 ergibt sich aus 10 - 1·7 = 3
     umgestellt: 10 = 3 + 1·7

100:7 = 14 Rest 2
   Der Rest 2 ergibt sich aus 100 - 14·7 = 100 - 98 = 2
     umgestellt: 100 = 2 + 14·7
   Nun ist 100 = 10·10 = 10·(3 + 1·7) = 30 + 70
   70 hat bei der Division durch 7 keinen Rest, die 30 aber hat die 2 als Rest.

1000:7 = 142 Rest 6
   Der Rest 6 ergibt sich aus 1000 - 142·7 = 1000 - 994 = 6
   Nun ist 1000 = 10·100 = 10·(2 + 14·7) = 20 + 140·7
   140·7 hat bei der Division durch 7 keinen Rest, die 20 aber hat die 6 als Rest.

Offensichtlich erhält man die gleichen Reste, wenn man statt der Zehnerpotenz nur das Zehnfache des letzten Restes dividiert. Damit werden die Zahlen wesentlich übersichtlicher, allerdings pflanzen sich eventuelle Fehler wieder fort.

Als Beispiel bestimmen wir die Periodenlänge von 1/43, parallel auf beide Arten. Zur Erinnerung: Wir suchen nach dem ersten Auftreten des Restes 1.

101 : 43 = 10 : 43 = 0 Rest 10 1 : 43 = 0 Rest 10
102 : 43 = 100 : 43 = 2 Rest 14 100 : 43 = 2 Rest 14
103 : 43 = 1000 : 43 = 23 Rest 11 140 : 43 = 3 Rest 11
104 : 43 = 10000 : 43 = 232 Rest 24 110 : 43 = 2 Rest 24
105 : 43 = 100000 : 43 = 2325 Rest 25 240 : 43 = 5 Rest 25
106 : 43 = 1000000 : 43 = 23255 Rest 35 250 : 43 = 5 Rest 35
107 : 43 = 10000000 : 43 = 232558 Rest 6 350 : 43 = 8 Rest 6
108 : 43 = 100000000 : 43 = 2325581 Rest 17 60 : 43 = 1 Rest 17
109 : 43 = 1000000000 : 43 = 23255813 Rest 41 170 : 43 = 3 Rest 41
1010 : 43 = 10000000000 : 43 = 232558139 Rest 23 410 : 43 = 9 Rest 23
1011 : 43 = 100000000000 : 43 = 2325581395 Rest 15 230 : 43 = 5 Rest 15
1012 : 43 = 1000000000000 : 43 = 23255813953 Rest 21 150 : 43 = 3 Rest 21
1013 : 43 = 10000000000000 : 43 = 232558139534 Rest 38 210 : 43 = 4 Rest 38
1014 : 43 = 100000000000000 : 43 = 2325581395348 Rest 36 380 : 43 = 8 Rest 36
1015 : 43 = 1000000000000000 : 43 = 23255813953488 Rest 16 360 : 43 = 8 Rest 16
1016 : 43 = 10000000000000000 : 43 = 232558139534883 Rest 31 160 : 43 = 3 Rest 31
1017 : 43 = 100000000000000000 : 43 = 2325581395348837 Rest 9 310 : 43 = 7 Rest 9
1018 : 43 = 1000000000000000000 : 43 = 23255813953488372 Rest 4 90 : 43 = 2 Rest 4
1019 : 43 = 10000000000000000000 : 43 = 232558139534883720 Rest 40 40 : 43 = 0 Rest 40
1020 : 43 = 100000000000000000000 : 43 = 2325581395348837209 Rest 13 400 : 43 = 9 Rest 13
1021 : 43 = 1000000000000000000000 : 43 = 23255813953488372093 Rest 1             130 : 43 = 3 Rest 1

1/43 besitzt folglich die Periodenlänge 21

Die Berechnung von 1017:43 gelingt mit normalen Taschenrechnern schon nicht mehr ohne Rundungsfehler. Die Vorteile des zweiten Verfahrens liegen also vor allem darin begründet.

 

Interaktive Beispiele

Nach oben beschriebenem Verfahren werden die Brüche zunächst optional gekürzt (ausprobieren und den Effekt überprüfen!), dann wird die Länge des unperiodischen Teils ermittelt, indem die Anzahl der 2en und 5en in der Primfaktorzerlegung ermittelt wird. Das geschieht durch wiederholtes Teilen des Nenners durch 2 und 5. Dann wird nach der kleinsten Zahl n gesucht, für die 10n bei der Division durch den verbleibenden Teil des Nenner den Rest 1 ergibt. Dazu wird das zweite Verfahren (Weiterrechnen mit dem Zehnfachen des vorherigen Rests) angewendet.

                 kürzen

 

Bei großen Nennern wird auch dieses Verfahren schnell unübersichtlich. Es lohnt daher, über weitere Vereinfachungen bzw. Einschränkungen nachzudenken. Schauen wir uns einmal die Periodenlängen von verschiedenen Primzahl-Nennern an:

m
(Primzahl)   
n
(Periodenlänge)
31
112
1716
4321
5313
5958
8944
9796
1014
12742
54791
88878886
8929144

Manchmal ist es die maximal mögliche Länge, nämlich m-1, die Anzahl der möglichen Reste bei der Division durch m (siehe oben), manchmal weniger. Gibt es eine Regel?

Wenn man die Periodenlänge mit der Zahl der möglichen verschiedenen Reste, also m-1, vergleicht, stellt man bei diesen Beispielen fest, daß die Periodenlänge n immer m-1 teilt!

     Pierre Fermat

Pierre Fermat

 

Plausibel wird diese Erscheinung durch folgende Überlegung:
Wenn das erste Auftreten der 1 die Periodenlänge angibt, dann wiederholen sich alle Reste im Abstand der Periodenlänge, also auch die 1.
Wenn nun die Periodenlänge immer ein Teiler von m-1 wäre, müßte der (m-1)te Rest ebenfalls immer die 1 sein. Und vor allem gälte umgekehrt: Wenn der (m-1)te Rest 1 ist, muß die Periodenlänge ein Teiler von m-1 sein.

Es fragt sich also nach der oben gewonnenen Erkenntnis, daß 10n den Rest 1 bei der Division durch m ergibt (mit n als Periodenlänge), ob n immer ein Teiler von m-1 sein muß, falls m eine Primzahl ist, bzw. ob 10m-1 dann immer den Rest 1 ergibt.

Daß 10p-1 bei der Division durch die Primzahl p tatsächlich immer den Rest 1 läßt, wenn p eine Primzahl und 10 teilerfremd zu p ist, hat bereits Pierre Fermat herausgefunden und bewiesen. Allgemein gilt das für alle Fälle np-1, wenn n nicht durch p teilbar ist. Es ist der sogenannte kleine Satz von Fermat, dessen Beweis hier zu finden ist.

Speziell läßt also nach Fermats Satz 10p-1 bei der Division durch p immer den Rest 1, woraus obige Vermutung folgt, daß die Periodenlänge bei allen Primzahl-Nennern p tatsächlich immer ein Teiler von p-1 ist.

Den kleinen Satz von Fermat hat Leonhard Euler auf alle natürliche Zahlen verallgemeinert, indem er p-1 durch die Anzahl aller möglichen Reste ersetzte, die mit dem Divisor keinen gemeinsamen Teiler besitzen. Das sind bei Primzahlen tatsächlich alle natürlichen Zahlen kleiner als die Zahl selbst, also p-1 Stück.

Leonhard Euler

Leonhard Euler

 

    

Bei zusammengesetzten Zahlen, die zwei oder mehrere unterschiedliche Primfaktoren haben, fallen jeweils die Vielfachen dieser Primzahlen heraus, z.B. sind die 3, 6, 9, 12, 15 und 18 sowie die 7 und die 14 nicht teilerfremd zur 21. Es sind 7-1 Vielfache der 3 und 3-1 Vielfache der 7, womit die Zahl der teilerfremden Reste 21-1 - 6 - 2 = 12 beträgt. Ist 12 nur zufällig gleich (7-1)·(3-1)? Nein!

Allgemein: Seien p und q die Primfaktoren von m, also m=p·q. Die Zahl der teilerfremden Reste ist dann p·q-1 - (p-1) - (q-1) = p·q - p - q + 1 = (p - 1)(q - 1).

Falls ein Primfaktor p mehrfach vorkommt, fallen noch mehr Reste heraus, die nicht teilerfremd sind. Bsp.: m=3·3·5=45:

Es fallen heraus 45/3-1=14 Vielfache der 3: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42
sowie 45/5-1=8 Vielfache der 5: 5, 10, 15, 20, 25, 30, 35, 40
Allerdings gibt es zwei gemeinsame Vielfache: 15 und 30; wobei sich das Zweifache aus dem zusätzlichen Primfaktor 3 ergibt.

Die Zahl der teilerfremden Reste ist damit
p·p·q-1 - (p·p·q/p-1) - (p·p·q/q-1) + (p-1) = p·p·q - 1 - p·q + 1 - p·p + 1 + p - 1 = p·p·q - p·q - p·p + p = p·(p - 1)·(q - 1)

Euler gab dieser Zahl der teilerfremden Reste von m die Bezeichnung φ(m).
Man sagt dazu φ-Funktion oder auch Eulersche Funktion. Das Zeichen φ ist der griechische Buchstabe phi.
φ(m) liest sich „phi von m“.

Allgemein ergibt sich φ(m) als Produkt aus allen vorkommenden um eins verminderten Primfaktoren (allerdings pro Primzahl nur einfach) und allen mehrfach auftretenden Primfaktoren.

Beispiele:
φ(280) = φ(2·2·2·5·7) = (2-1)·2·2·(5-1)·(7-1) = 2·2·4·6 = 96
φ(281) = 281-1 = 280
φ(282) = φ(2·3·47) = (2-1)·(3-1)·(47-1) = 2·46 = 92

  φ( )  = 

 

Periodenlänge und φ-Funktion

Es stellt sich heraus, daß die Periodenlänge n beliebiger Nenner m, die nicht durch 2 und/oder 5 teilbar sind, stets ein Teiler der Anzahl zu m teilerfremder Reste bei der Division durch m ist, d.h.: n|φ(m).

Weil sich die Reste (siehe oben) aus 10i:m ergeben und m keinen gemeinsamen Teiler mit 10 hat, kommen auch keine Reste infrage, die einen gemeinsamen Teiler mit m haben.

Beweis: 10i : m = x Rest r läßt sich so schreiben: 10i = x·m + r. Angenommen, es gäbe einen gemeinsamen Teiler t von m und r. Dann gibt es natürliche Zahlen a und b mit a·t=m und b·t=r. Man kann dann schreiben: 10i = x·a·t + b·t = t·(x·a + b). Daraus folgt, daß 10i durch t teilbar ist. 10i besitzt aber nur die Primfaktoren 2 und 5, wohingegen t als Teiler von m durch keine dieser Primfaktoren teilbar sein darf, denn aus m sind alle 2en und 5en gekürzt. Aus diesem Widerspruch folgt, daß es keinen solchen Teiler t geben kann!

Damit ist die maximale Anzahl der möglichen Reste tatsächlich φ(m) und die Periodenlänge nach dem Satz von Fermat/Euler ein Teiler von φ(m).

Es reicht also aus, für alle Teiler t von φ(m) zu prüfen, ob 10t bei der Division durch m den Rest 1 läßt. Hierzu muß man allerdings die Primfaktorzerlegung von m kennen, um φ(m) berechnen zu können. Außerdem benötigte man eine Möglichkeit, die Reste von 10t bei der Division durch m bequemer zu bestimmen. Und diese Möglichkeit gibt es, wie wir gleich sehen werden.

Dazu führen wir für das Rechnen mit Divisionsresten zunächst noch eine andere Schreibweise ein.

 

„Modulo“ statt „Rest bei Division“

Anstelle von „r ist Rest bei der Division von a durch m“ sagt man auch „a ist kongruent r modulo m“ bzw. a r mod m. Alle Zahlen, die bei der Division durch eine Zahl m, den sogenannten Modul, den gleichen Rest lassen, sind kongruent modulo m.

Beispiel: 12 und 87 sind kongruent modulo 5, denn beide lassen den Rest 2 bei der Division durch 5.
12 87 mod 5.

Man kann, wenn das Ergebnis modulo m genommen werden soll, bei den Grundrechenarten jeden Einzelschritt und jede einzelne Zahl modulo m nehmen.

Zahlenbeispiele:
Addition: 5+7 (5 mod 3)+(7 mod 3) mod 3, denn 5+7 = 12 0 mod 3 und (5 mod 3)+(7 mod 3) = 2+1 = 3 0 mod 3.
Multiplikation: 5·7 (5 mod 3)·(7 mod 3) mod 3, denn 5·7 = 35 2 mod 3 und (5 mod 3)·(7 mod 3) = 2·1 = 2 2 mod 3.

Wegen a·b (a mod m)·(b mod m) mod m, ist ab+c mod m (ab mod m)·(ac mod m) mod m, d.h. auch dieses Potenzgesetz gilt in der Moduloarithmetik.

Zahlenbeispiel:
52+3 mod 7 (52 mod 7)·(53 mod 7) mod 7, denn 52+3 = 55 = 3125 3 mod 7 und (52 mod 7)·(53 mod 7) = (25 mod 7)·(125 mod 7) = 4·6 = 24 3 mod 7.

Daraus ergibt sich die Möglichkeit, Ausdrücke wie 10i mod m einfacher zu berechnen, indem bei der Potenzierung 10i bereits jede einzelne Multiplikation modulo m durchgeführt wird.

Eine weitere Idee bringt eine erhebliche Reduzierung des Rechenaufwandes bei großen Exponenten:
Man zerlegt den Exponenten in seine Binärdarstellung, dann kann man die Potenz sukzessive durch Quadrieren berechnen und muß nur dort mit der Basis multiplizieren, wo die entsprechende Binärstelle besetzt ist. Siehe dazu die Erläuterungen zur Verwendung des Horner-Schemas auf der Seite zur Umrechnung von Zahlensystemen. Das dort beschriebene Verfahren ist hierzu sehr ähnlich.

Beispiel:
Wegen 1023 = 1016+4+2+1 = 1016·104·102·101
und
23 = 1·24 + 0·23 + 1·22 + 1·2 + 1 = (((1·2 + 0)·2 + 1)·2 + 1)·2 + 1,
gilt:
1023 = 10(((1·2 + 0)·2 + 1)·2 + 1)·2 + 1
und man kann so vorgehen:

Berechnung des Exponenten 23 (durch Addieren und Verdoppeln):

             Anfangswert 0

Binärstelle  besetzt addieren   ergibt   verdoppeln

    4          x        +1         1          
                                              2
    3                   /          2
                                              4 
    2          x        +1         5
                                             10
    1          x        +1        11
                                             22
    0          x        +1        23

Analoge Berechnung der Potenz 1023 (durch Multiplizieren und Quadrieren):

             Anfangswert 1

Binärstelle  besetzt multiplizieren   ergibt    quadrieren

    4          x         ·10            101          
                                                   102
    3                     /             102
                                                   104 
    2          x         ·10            105
                                                   1010
    1          x         ·10            1011
                                                   1022
    0          x         ·10            1023

Alle Operationen können mod m durchgeführt werden, d.h. man kann nach jeder Multiplikation statt mit dem Produkt selbst mit dem Rest bei der Division des Produkts durch m weitermachen und selbst die Faktoren modulo m nehmen.

Interaktive Beispiele

Berechne:   hoch mod   =      

→ Umwandeln vom Dezimal- ins Binärsystem

 

Berechnung der Periodenlänge

Mit diesen Hilfsmitteln läßt sich die Periodenlänge für m also bestimmen, indem man für jeden Teiler t von φ(m) prüft, ob 10t = 1 mod m ist.

Hinweis: Die folgenden Scripts sind beschränkt auf Nenner bis 9999999

m =      

Auch in anderen Zahlensystemen als dem Dezimalsystem gibt es eine Ziffern-Darstellung von gebrochenen Zahlen mit Komma. → Ausprobieren auf dieser Seite. Die Periodenbildung in andern Stellenwertsystemen unterliegt analogen Gesetzmäßigkeiten wie den hier beschriebenen. Insbesondere kann die Periodenlänge mit demselben Verfahren berechnet werden, wenn als Basis anstelle der 10 die entsprechende Basis des Zahlensystems verwendet wird. Neue Basis:

 

Im folgenden Script kann nunmehr die Dezimalbruchentwicklung einschließlich kompletter Periode von Brüchen berechnet werden. Die Periodenlänge wird dabei vom Script nach dem beschriebenen Verfahren und mit den in den vorigen Beispielen verwendeten Funktionen berechnet.

             Eingabe im o.a. Zahlensystem
Eingabe immer im Dezimalsystem
 
      bzw. Entwicklung nach der oben eingegebenen Zahlenbasis

Hinweis: Sehr lange Perioden können eventuell die Anzeigekapazität des Textfeldes überfordern.

→ Fenster zur kompletten Darstellung der schriftlichen Division öffnen
→ Rechner mit „beliebig“ vielen Kommastellen

 


Version: 6. 7. 2005 (zuletzt leicht korrigiert am 18. 10. 2010)
© Arndt Brünner, 14. 2. 2003
Kleiner Satz von Fermat
Tabelle der Periodenlängen bis 10000
div. Rechner zur Bruchrechnung
endliche Kettenbrüche
Umwandeln von periodischen Dezimalbrüchen in Brüche
Primzahlseite mit Primfaktorzerlegung u.v.m.
Matheseiten-Übersicht
Forum
Gästebuch
zurück