Kongruenz (Zahlentheorie)
Dieser Artikel enthält mathematische Symbole. Diese werden in der Tabelle mit mathematischen Symbolen erläutert.In der Zahlentheorie heißen zwei ganze Zahlen a und b kongruent modulo m (wobei m eine positive ganze Zahl ist), wenn m die Differenz (a-b) teilt. Man schreibt:
Anders formuliert kann man auch sagen, dass zwei Zahlen kongruent modulo einer Zahl m sind, wenn sie bei der Division durch m den selben Rest ergeben.
Beispiele:
- 3 ≡ 24 mod 7, denn 7 teilt -21 (=3-24)
- -31 ≡ 11 mod 7, denn 7 teilt -42 (=-31-11)
- -15 ≡ -64 mod 7, denn 7 teilt 49 (=-15-(-64))
Es gibt daher genau m Restklassen () modulo m.
Beispiel:
- Modulo 2 sind die beiden Restklassen die Menge der geraden Zahlen () und die Menge der ungeraden Zahlen ().
Die Theorie der Kongruenzen wurde von Carl Friedrich Gauß im Jahre 1801 in seinem Werk Disquisitiones Arithmeticae begründet.
Table of contents |
2 elementare Rechenregeln 3 abgeleitete Rechenregeln 4 Anwendungen 5 Weblinks |
Veranschaulichen kann man das Rechnen mit Restklassen anhand des Ziffernblattes einer Analoguhr. Die Stunden sind von 1 bis 12 nummeriert, wobei Stunde 12 als Stunde 0 betrachtet wird.
Beginnt man bei Stunde 0 und addiert jeweils eine Stunde, erhält man der Reihe nach jede der 12 Stunden des Ziffernblattes.
Man addiert zwei beliebige Stunden miteinander, indem man bei der ersten angegebenen Stunde beginnt und im Uhrzeigersinn die zweite Stundenangabe abzählt: Um 4 + 5 zu ermitteln, beginnt man bei Stunde 4 und zählt 5 Stunden weiter, man landet bei Stunde 9. Berechnet man nun 9 + 5, zählt also von Stunde 9 aus 5 Stunden weiter, landet man bei Stunde 2, es ist also 9 + 5 = 2 in diesem System. Wie kommt dieses Ergebnis zustande? Addiert man einfach die Stundenwerte, erhält man 14; und "14 Uhr" stimmt auf dem zwölfstündigen Ziffernblatt mit "2 Uhr" überein, also ist hier 14 = 2. Das Ergebnis einer Addition ist also die normale Summe, eventuell abzüglich einer 12. Dies entspricht dem Rest bei Division durch 12. Diese Art der Addition heißt "Addition modulo 12".
Man erkennt hier, dass die Addition der 12 eine Zahl nicht verändert, 12 + x = x für jede Stunde x. Das erklärt, warum die 12. Stunde hier als Stunde 0 bezeichnet wird.
Die Multiplikation wird auf die Addition zurückgeführt: Um z.B. 4 · 3 zu bestimmen, bildet man die Summe 3 + 3 + 3 + 3, und landet bei der 12. Stunde. Das Produkt 4 · 4 liefert "16 Uhr", und das ist identisch mit "4 Uhr"; modulo 12 ist also 4 · 4 = 4.
Die 12 Stundenwerte, zusammen mit den Regeln für Addition und Multiplikation, schreibt man als (Z/12Z, +, ·).
Was für 12 geht, funktioniert auch für jede andere natürliche Zahl n. In Z/4Z = {0, 1, 2, 3} ist 1 = 1, 2 = 1 + 1, 3 = 1 + 1 + 1, 0 = 1 + 1 + 1 + 1.
Für das Rechnen mit Kongruenzen lassen sich einige elementare Rechenregeln aufstellen:
Gilt a ≡ b (mod m) und c ≡ d (mod m) und b ≡ x (mod m), so gilt:
Mit Hilfe von Kongruenzen lassen sich zum Beispiel die Teilbarkeitsregeln leicht beweisen. Eine wichtige Aussage über Kongruenzen von Primzahlen ist der kleine Satz von Fermat bzw. der Fermatsche Primzahltest.
Ferner sind Kongruenzen bzw. Restklassen oft hilfreich, wenn man Berechnungen mit sehr großen Zahlen durchführen muss.
Siehe auch: lineare Kongruenz, simultane Kongruenz, chinesischer Restsatz
Frage: Mit welcher Ziffer endet die Zahl 333222?
Es ist 333 ≡ 3 mod 10. Daraus folgt mit der Potenzregel (a=333, b=3, m=10, n=222): 333222 ≡ 3222 mod 10.
Es gilt 32 ≡ (-1) mod 10. Erneute Anwendung der Potenzregel (a=32, b=-1, m=10, n=111) liefert: 3222 = 32*111 ≡ (-1)111 = -1 ≡ 9 mod 10.
Antwort: Die Endziffer lautet 9.
Frage: Ist 220-1 durch 41 teilbar?
Man sieht leicht: 25 ≡ -9 mod 41.
Antwort: 220-1 ist durch 41 teilbar.
Behauptung: 2340-1 ist durch 341 teilbar.
Von dieser Eigenschaft ist im Artikel Fermatscher Primzahltest die Rede. Sie besagt, dass die Zahl 341 pseudoprim zur Basis 2 ist.
Beweis: 210 = 1024 = 3·341 + 1 ≡ 1 mod 341.
Frage: Welches ist der Rest, wenn man die Summe s(9999) := 1! + 2! + 3! + ... +9999! durch 12 teilt?
Es gilt: 4! = 1·2·3·4 ≡ 0 mod 12.
Antwort: Wenn man s(9999) durch 12 teilt, dann bleibt als Rest 9 übrig.
siehe auch: ModuloVeranschaulichung am Ziffernblatt der Uhr
elementare Rechenregeln
Weiterhin gilt für das Rechnen mit Restklassen:abgeleitete Rechenregeln
Sind c und n teilerfremd, also d = 1, dann folgt sofort a ≡ b mod n
Mit anderen Worten: Teilt man a2 durch 8, dann bleibt als Rest 1.
Mit anderen Worten: Entweder a3 ist durch 9 teilbar oder es bleibt als Rest 1 oder 8.
Mit anderen Worten: Teilt man a3 durch 6, dann bleibt als Rest die Zahl a selbst.
Mit anderen Worten: Entweder a3 ist durch 7 teilbar oder es bleibt als Rest 1 oder 6.
Mit anderen Worten: Entweder a4 ist durch 5 teilbar oder es bleibt als Rest 1
:
Anwendungen
Beispiel 1
Beispiel 2
Daraus folgt mit der Potenzregel (a=25, b=-9): (25)4 ≡ (-9) 4mod 41 = 81·81 mod 41.
Andererseits gilt: 81 ≡ -1 mod 41. Die Potenzregel liefert 812 ≡ (-1)2 mod 41 = 1 mod 41.
Insgesamt ergibt sich nun: 220-1 ≡ 81·81 mod 41 -1 ≡ (1 mod 41) mod 41 - 1 = 1 - 1 = 0Beispiel 3
2340 = (210)34 ≡ 117 mod 341 = 1 mod 341
Daraus folgt: 2340-1 ≡ 1 mod 341 -1 = 0Beispiel 4
Gesucht ist als n mit s(9999) ≡ n mod 12.
Daraus folgt mit der Multiplikationsregel für k > 3: k! = 4!·5·6···k ≡ 0·5·6··k mod 12 = 0 mod 12.
Anwendung der Additionsregel liefert s(9999) = 1! + 2! + 3! + 4! + ... + 9999! ≡ 1! + 2! + 3! + 0 mod 12 = 9 mod 12.
Aus der Herleitung folgt allgemeiner: s(k) ≡ 9 mod 12 für alle k > 3.