Nr. 2 / Oktober 2004
Früher wurde in der Schule eine Methode gelehrt, mit der man lange Rechnungen kontrollieren konnte: die sogenannte Neunerprobe. Das ging so:
Man findet den Neunerrest einer Zahl, indem man ihre Ziffern addiert. Ist das Ergebnis größer als 9, so addiert man die Ziffern wieder - so lange, bis nur mehr eine einstellige Zahl übrigbleibt.
Beispiel: Neunerrest von 2375: 2 + 3 + 5 + 7 = 17, 1 + 7 = 8
Man kann sich dabei Rechenarbeit ersparen, indem man 9er oder Ziffern,
die zusammen 9 ergeben, gleich weglässt:
Neunerrest von 1932 (9 weggelassen): 1 + 3 + 2 = 6
Neunerrest von 365 (3 + 6 = 9 weggelassen): 5
Wenn man jetzt eine lange Addition kontrollieren will, addiert man einfach die Neunerreste der Summanden. Das Ergebnis muss gleich dem Neunerrest der Summe sein:
2375 1932 365 ---- 4672
Neunerprobe: 8 + 6 + 5 = 19, Neunerrest 1
Neunerrest von 4672: 4 + 6 = 10, 1 + 0 = 1
Das funktioniert auch bei Multiplikationen:
2375*365 -------- 7125 14250 11875 ------ 866875
Neunerprobe: 8*5 = 40, Neunerrest 4
Neunerrest von 866875: 8 + 6 + 6 + 8 + 7 + 5 = 40, 4 + 0 = 4
Warum funktioniert die Neunerprobe?
Dahinter steckt folgende Idee: Man fasst alle Zahlen, die bei der Division durch 9 denselben Rest lassen, zu einer Menge zusammen.
[0] = {0, 9, 18, 27, ... }
[1] = {1, 10, 19, 28, ... }
[2] = {2, 11, 20, 29, ... }
[3] = {3, 12, 21, 30, ... }
[4] = {4, 13, 22, 31, ... }
[5] = {5, 14, 23, 32, ... }
[6] = {6, 15, 24, 33, ... }
[7] = {7, 16, 25, 34, ... }
[8] = {8, 17, 26, 35, ... }
Eine solche Menge nennt man eine Restklasse modulo 9. Zwei Zahlen, die in derselben Restklasse liegen, heißen kongruent modulo 9. Man schreibt zum Beispiel:
20 º 2 mod 9
Wenn wir jetzt etwa eine Zahl aus [2] und eine Zahl aus [3] addieren, ist das Ergebnis immer aus [5]. Und wenn wir eine Zahl aus [2] und eine Zahl aus [3] miteinander multiplizieren, ist das Ergebnis immer aus [6]. Das gilt auch für alle anderen Zahlen. Wir können also mit Restklassen genauso rechnen wie mit natürlichen Zahlen! Wir müssen nur Ergebnisse, die größer oder gleich 9 sind, durch ihren Rest bei der Division durch 9 ersetzen.
Für die, die's genau wissen wollen, ist hier der Beweis:
Eine Zahl a aus der Restklasse [2] können wir in folgender Form schreiben: a = 9m + 2 (dabei ist m eine natürliche Zahl).
Genauso schreiben wir für eine Zahl b aus [3]: b = 9n + 3.
Die Summe ist dann a + b = (9m + 2) + (9n + 3) = 9(m + n) + 5
und das Produkt a*b = (9m + 2)*(9n + 3) = 81mn + 9m + 9n + 6 = 9(9mn + m + n) + 6.
Wir haben also bei der Neunerprobe einfach modulo 9 gerechnet. Jetzt
müssen wir uns noch überlegen, dass die Ziffernsumme einer Zahl
wirklich gleich ihrem Neunerrest ist. Das zeigt man so: Es ist
10 º 1 mod 9
100 º 1 mod 9
1000 º 1 mod 9 usw.,
also z.B. 2375 = 2*1000 + 3*100 + 7*10 + 5
º 2 + 3 + 7 + 5 mod 9.
Jetzt könnt ihr sicher diesen netten Trick erklären:
http://www.prophezeiungsforum.de/scripte/
Gedankenleser.htm
Wir wollen noch etwas genauer untersuchen, wie man mit Restklassen rechnet. Dazu stellen wir einmal eine Additions- und eine Multiplikationstabelle modulo 5 auf. (Wenn man weiß, dass Restklassen gemeint sind, kann man die eckigen Klammern auch weglassen.)
|
|
Wir stellen zunächst einmal fest, dass die Restklassenaddition und -multiplikation, genauso wie die normale Addition und Multiplikation, kommutativ und assoziativ sind. (Das Assoziativgestz kann man an einigen Beispielen überprüfen, z.B.: (2*3)*4 = 1*4 = 4, 2*(3*4) = 2*2 = 4.)
Wir können modulo 5 auch subtrahieren: wenn wir z.B. 2 - 3 mod 5 berechnen wollen, fragen wir: 3 plus wieviel ist 2? (Wir suchen also in der Zeile "3" der Additionstabelle die Zahl 2.) Aus der Tabelle lesen wir ab, dass das Ergebnis 4 ist.
Einfacher geht es, wenn wir zuerst zu jeder Zahl die "negative"
suchen:
0 + 0 = 0 Þ -0 = 0
1 + 4 = 0 Þ -1 = 4, -4 = 1
2 + 3 = 0 Þ -2 = 3, -3 = 2
Dann können wir rechnen: 2 - 3 = 2 + (-3) = 2 + 2 = 4
Sogar die Division modulo 5 ist möglich: Wir wollen z.B. 3:4 berechnen. Dazu fragen wir: 4 mal wieviel ist 3? (Wir suchen also in der Zeile "4" der Multiplikationstabelle die Zahl 3.) Das Ergebnis ist 2, denn 4*2 = 3. (Durch 0 darf man natürlich nicht dividieren.)
Auch hier ist es einfacher, wenn wir zuerst zu jeder Zahl den
"Kehrwert" suchen:
1*1 = 1 Þ 1/1 = 1
2*3 = 1 Þ 1/2 = 3, 1/3 = 2
4*4 = 1 Þ 1/4 = 4
Dann rechnen wir: 3:4 = 3*(1/4) = 3*4 = 2
Wir können also modulo 5 auch lineare Gleichungen lösen, z.B.:
3x + 2 = 1 |+3 (-2 = 3)
3x = 4 |*2 (1/3 = 2)
x = 3
Nun sehen wir uns noch die Additions- und Multiplikationstabelle modulo 6 an:
|
|
Bei der Addition, Subtraktion und Multiplikation gibt es nichts Neues, aber die Division kann Probleme machen. Die Rechnung 5:2 kann z.B. nicht ausgeführt werden, denn es gibt keine Zahl, die mit 2 multipliziert 5 ergibt. Es gibt auch nicht zu jeder Zahl einen "Kehrwert", sondern nur zu 1 und 5, weil die 1 nur in diesen beiden Zeilen auftaucht.
Der Unterschied zum vorigen Beispiel ist der, dass 5 eine Primzahl ist, 6 aber nicht. Die Restklassendivision ist also nur modulo einer Primzahl uneingeschränkt möglich. (Im nächsten Newsletter möchte ich euch mehr über Primzahlen erzählen.)
Man kann natürlich auch Potenzen von Restklassen berechnen. Das
Potenzieren kann aber nur schwer rückgängig gemacht werden - bei
großen Zahlen ist das so gut wie unmöglich. Darauf beruht ein
Verfahren zur Verschlüsselung von Daten, der RSA-Algorithmus:
Der Absender wandelt seine Nachricht in eine Zahl um und potenziert diese
mit einer anderen Zahl, dem "öffentlichen Schlüssel" des
Empfängers. Dieser muss das Ergebnis mit einer weiteren Zahl,
seinem "privaten Schlüssel" potenzieren, um wieder die
ursprüngliche Nachricht zu erhalten. (Alle Rechnungen werden modulo
einer genügend großen Zahl n durchgeführt.) Wenn man den
privaten Schlüssel nicht kennt, ist es unmöglich, die Nachricht
zu entschlüsseln.
Mehr über das Rechnen mit Restklassen, vor allem über die
Berechnung von hohen Potenzen, findet ihr hier:
http://www.zum.de/Faecher/Materialien/dorner/
manuskripthtml/kongruenzen/kongruenzen.html
Und zum RSA-Algorithmus:
http://de.wikipedia.org/wiki/RSA-Kryptosystem
Viel Spass bis zum nächsten Mal!
Jutta