Kongruenzen (Modulare Arithmetik)

This wiki article doesn't exist in English. We will display it in German for you instead.

Written by Lazar Todorovic.

In diesem Kapitel führen wir den Begriff der “Kongruenzen” ein und erkunden, wie man mit ihnen rechnen kann (“modulare Arithmetik”). Ausserdem stellen wir den Euklidischen Algorithmus und seine Anwendungen vor.

Wenn im Folgenden von “Zahlen” die Rede ist, sind immer nicht-negative ganze Zahlen gemeint: 0, 1, 2, …

Ein allgemein bekanntes Beispiel für Kongruenzbeziehungen sind gerade und ungerade Zahlen. Gerade Zahlen sind ohne Rest (bzw. mit Rest 0) teilbar durch 2, während bei ungeraden ein Rest von 1 zurückbleibt, wenn man sie durch 2 teilt. Wenn zwei Zahlen bei der Division durch 2 den gleichen Rest haben, nennen wir sie kongruent modulo 2. Entsprechend sind alle geraden Zahlen kongruent modulo 2 zueinander, und ebenso alle ungeraden.

Diese Betrachtung muss natürlich nicht auf Division durch 2 beschränkt bleiben. Zwei Zahlen, nennen wir sie aa und bb, sind kongruent modulo nn, wenn sie den gleichen Rest bei der Division durch nn haben. Dabei wird nn als Modul bezeichnet und kann eine beliebige Zahl sein, solange sie grösser als 0 ist. Die mathematische Notation dafür ist

ab(modn).a \equiv b (\mod n).

Die Restklasse von aa (modulo nn) besteht aus allen Zahlen, die kongruent zu aa (modulo nn) sind. Aus diesem Grund ist “aa ist kongruent zu bb (modulo nn)” gleichbedeuted mit “aa gehört (modulo nn) der gleichen Restklasse an wie bb.” Eine Restklasse wird normalerweise mit der kleinsten Zahl bezeichnet, die in ihr vorkommt. Die Bezeichnung der Restklasse von aa modulo nn ist also genau der Rest der Division von aa durch nn. Modulo 2 gibt es die Restklassen 0 und 1. Allgemein gibt es modulo nn genau nn verschiedene Restklassen, nämlich die von 0, 1, …, n1n-1. Die Restklasse von nn ist wieder die gleiche wie die von 0. Was ist die Restklasse von n+1n+1?

Allgemein gilt, dass sich die Restklasse einer Zahl modulo nn nicht ändert, wenn man ein Vielfaches des Moduls nn zu ihr dazuaddiert oder subtrahiert; die folgende Kongruenz ist also für beliebige Zahlen a,ca, c und nn erfüllt (wobei cc auch negativ sein darf):

a+cna(modn).a + cn \equiv a (\mod n).

Umgekehrt kann jede Zahl, die in der gleichen Restklasse wie aa ist, als a+cna+cn geschrieben werden, also als Summe von aa und einem Vielfachen von nn. Dies bedeutet, dass zwei Zahlen genau dann in der gleichen Restklasse sind, wenn ihre Differenz ein Vielfaches des Moduls nn ist. Wenn man Restklassen auf diese Weise definiert, ist es ausserdem klar, was die Restklasse einer negativen Zahl ist.

Du kennst vielleicht den Operator % aus C++ und ähnlichen Sprachen. Der Ausdruck a%n liefert dort den Rest der Division von aa durch nn. Alternativ kann man es auch so sehen, dass dieser Operator die kleinste Zahl zurückgibt, welche in der Restklasse von aa modulo nn ist.

Rechnen mit Restklassen

Addition Das spannende an Restklassen ist, dass man mit ihnen in vielerlei Hinsicht gleich rechnen kann wie mit Zahlen. Betrachte als Beispiel die folgende Kongruenz:

7+90(mod4).7 + 9 \equiv 0 (\mod 4).

Wie oben erwähnt, ändert sich die Restklasse einer Zahl nicht, wenn man ein Vielfaches des Moduls zu ihr dazuaddiert. Wir können also auf jeder Seite der Beispielkongurenz beliebig Vielfache von 4 dazuaddieren, ohne dass sie ihre Gültigkeit verliert. Wir erhalten so z.B.

7+912=(74)+(98)=3+10(mod4).7+9-12 = (7-4) + (9-8) = 3+ 1 \equiv 0 (\mod 4).

Indem man statt 12 eine anderes, geeignetes Vielfaches von 4 nimmt, kann man beide Summanden durch ein beliebiges Mitglied ihrer jeweiligen Restklasse ersetzen. Normalerweise will man die Summanden durch das kleinste Mitglied ihrer Restklasse ersetzen.

Beispiel: Auch wenn dies alles bislang recht abstrakt scheint (und es durchaus auch ist), so gibt es doch auch aus dem Alltag Beispiele für Rechnung mit Kongruenzen und Restklassen. Das wohl bekannteste davon kommt aus der Zeitrechnung.

(Bild: Wikipedia) Der Stundenzeiger einer Uhr gibt die Restklasse der gegenwärtigen Stunde modulo 12 an. Ebenso gibt der Minutenzeiger die Restklasse der gegenwärtigen Minute modulo 60 an. Welche Information gibt der Sekundenzeiger? Beachte, dass in diesem Fall die Restklasse jeweils die einzige vermittelte Information ist. Bei anderen Formen der Zeitrechnung (Jahresangaben, UNIX-Zeitstempel) ist dies anders. Beim Rechnen mit Stunden ist es ganz natürlich, so vorzugehen wie im vorherigen Absatz beschrieben. Wenn wir “sieben Stunden nach 11 Uhr”, also 11+7(mod12)11+7 (\mod 12) berechnen, ersetzen wir das Ergebnis durch die kleinste Zahl seiner Restklasse: Aus 11+7=1811+7=18 wird 66 (Uhr). Ebenso können wir auch die Summanden ersetzen, z.B. wenn wir “21 Stunden nach 19 Uhr” bestimmen wollen. Dann wird 19+21(mod12)19+21 (\mod 12) zu 7+9(mod12)7 + 9 (\mod 12), abschliessend wird das Ergebnis von 1616 zu 44 (Uhr).

Multiplikation Für Multiplikationen gelten ähnliche Eigenschaften wie bei der Addition, wie wir etwas formaler zeigen werden. Wir betrachten die Multiplikationen zweier Zahlen aa und bb modulo nn. Wir ersetzen aa durch a+c1na+c_1n, welches für jede beliebige Zahl c1c_1 in der gleichen Restklasse wie aa ist. Analog ersetzen wir bb durch b+c2nb+c_2n, wobei wiederum c2c_2 eine beliebige Zahl ist. Untersuchen wir nun, ob die folgende Kongruenz erfüllt ist:

(a+c1n)(b+c2n)ab(modn),(a+c_1n)(b+c_2n) \equiv ab (\mod n),

also ob die Restklasse des Produkts abab sich ändert, wenn wir die Faktoren durch andere Mitglieder ihrer jeweiligen Restklasse ersetzen. Dazu können wir erst einmal ausmultiplizieren:

(a+c1n)(b+c2n)=ab+ac2n+c1bn+c1c2n2ab(modn).(a+c_1n)(b+c_2n) = ab + ac_2n+c_1bn+ c_1c_2n^2 \equiv ab (\mod n).

Beachte, dass ac2n+c1bn+c1c2n2=n(ac2+c1b+c1c2n)ac_2n+c_1bn+ c_1c_2n^2 = n(ac_2+c_1b+ c_1c_2n) immer ein Vielfaches von nn ist. Wir können es also von der linken Seite abziehen, ohne die Restklasse zu ändern, sprich

ab+n(ac2+c1b+c1c2n)ab+n(ac2+c1b+c1c2n)n(ac2+c1b+c1c2n)=ab(modn).ab+n(ac_2+c_1b+ c_1c_2n) \equiv ab+n(ac_2+c_1b+ c_1c_2n)-n(ac_2+c_1b+ c_1c_2n) = ab (\mod n).

Die Eigenschaft, dass es bei der Addition und Multiplikation nicht darauf ankommt, welches Mitglied einer Restklasse man nimmt, ist bei der Modulo-Rechnung am Computer (und beim Lösen von vielen SOI-Aufgaben) ziemlich praktisch. Häufig besteht eine Aufgabe daraus, die Restklasse einer unter Umständen sehr grossen Zahl zu bestimmen, die selber nicht als 64-bit Ganzzahl dargestellt werden kann.

Beispiel: Berechne die kleinste Zahl in der Restklasse von 242434546+1(mod1337)2^{42'434'546}+1 (\mod 1337). Ein ersten Ansatz wäre, zuerst 242434546+12^{42'434'546}+1 zu berechnen, z.B. mit der Funktion pow. In C++ würde dies aber fehlschlagen, weil dort alle eingebauten Funktionen nur mit den Standard-Datentypen arbeiten, die aber alle zu klein sind um 242434546+12^{42'434'546}+1 exakt darzustellen. (Der Typ double, mit dem die Funktion pow arbeitet, kann zwar auch Zahlen darstellen, die viel grösser sind als 2642^{64}, macht dann aber Rundungsfehler.) Mit einem Datentyp BigInt, der beliebig grosse Zahlen unterstützt, könnte man im Prinzip das Ergebnis wie folgt berechnen:

BigInt a = 1;
for (int k = 1; k <= 42434546; k++)
    a = 2*a;
return (a+1)%1337;

Dieser Ansatz ist aus verschiedenen Gründen recht ineffizient. Übliche Implementationen des Datentyps BigInt würden für die Darstellung der Zahl 242434546+12^{42'434'546}+1 ganze 4243454742'434'547 Bits, d.h. mehr als 5MB benötigen. Das ist so viel, dass sogar eine einfache Operation wie die Multiplikation mit zwei ziemlich viel Zeit in Anspruch nehmen würde, von der Verkettung von 4243454642'434'546 solcher Operationen ganz zu schweigen. Der Einsatz von BigInt ist aber gar nicht notwendig; wir brauchen nur zu wissen, welche Restklasse modulo 1337 das Resultat hat. Aus diesem Grund können wir jedes Zwischenergebnis wie im vorherigen Absatz beschrieben durch das kleinste Mitglied seiner Restklasse ersetzen. So müssen wir nie mit Zahlen rechnen, die grösser sind als 213372\cdot 1337. Der obige Code kann also durch den folgenden ersetzt werden:

int a = 1;
for (int k = 1; k <= 42434546; k++)
    a = (2*a)%1337;
return (a+1)%1337;

Wir kommen später darauf zu sprechen, wieso die Laufzeit auch dieser Variante noch bei weitem nicht optimal ist.

Zusammenfassend können wir sagen, dass in C++ für (fast) beliebige ints a, b und n die folgenden Ausdrücke wahr (d.h. true) sind:

( a + b ) % n == ( (a%n) + (b%n) ) % n
( a * b ) % n == ( (a%n) * (b%n) ) % n

Dies kann nur fehlschlagen, wenn irgendwo ein Überlauf passiert, also wenn z.B. das Resultat von (a%n) * (b%n) (oder irgendeiner der anderen Additionen/Multiplikationen) zu gross ist, um als int dargestellt zu werden.

Subtraktion Die Subtraktion von Restklassen funktioniert genau gleich wie die Addition. Beim Programmieren muss man aber beachten, dass das Ergebnis von a%n nicht in allen Programmiersprachen gleich ist, wenn aa negativ ist. So ist es in C++ immer negativ und man muss nn zum Ergebnis dazuzählen, um das kleinste nicht-negative Mitglied der Restklasse zu erhalten, d.h. man benutzt in diesem Fall a%n+n.