Matheseiten-�bersicht Berechnung der Periodenl�nge von Dezimalbr�chenBeim 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 PeriodeDa 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 10000Wenn man eine nat�rliche Zahl durch Potenzen von 10 teilt, entsteht also 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 1000Nur 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 1000000,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 7000Wegen 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 PeriodeDie 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. Weiter: Die 12 entsteht aus 90-78 =
90-6�13. Nun gut aufgepa�t! Weiter: Der n�chste Rest 3 entsteht aus 120-117 = 120-9�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
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.
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. 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:
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!
Plausibel wird diese Erscheinung durch folgende �berlegung: 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.
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 Die Zahl der teilerfremden Reste ist damit Euler gab dieser Zahl der teilerfremden Reste von m die Bezeichnung φ(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: Periodenl�nge und φ-FunktionEs 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.
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. Man kann, wenn das Ergebnis modulo m genommen werden soll, bei den Grundrechenarten jeden Einzelschritt und jede einzelne Zahl modulo m nehmen. Zahlenbeispiele: 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: 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: Beispiel: 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 1023Alle 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. Hinweis: Sehr lange Perioden k�nnen eventuell die Anzeigekapazit�t des Textfeldes �berfordern. → Fenster zur kompletten Darstellung der schriftlichen Division
�ffnen Version: 6. 7. 2005 (zuletzt leicht korrigiert am 18. 10. 2010) |
5 gleiche ziffern ergeben 1000
zusammenhängende Posts
Urheberrechte © © 2024 ketiadaan Inc.
