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 $a$ und $b$ , sind kongruent modulo $n$ , wenn sie den gleichen Rest bei der Division durch $n$ haben. Dabei wird $n$ als Modul bezeichnet und kann eine beliebige Zahl sein, solange sie grösser als 0 ist. Die mathematische Notation dafür ist

a \equiv b (\mod n).

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

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

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

Umgekehrt kann jede Zahl, die in der gleichen Restklasse wie $a$ ist, als $a+cn$ geschrieben werden, also als Summe von $a$ und einem Vielfachen von $n$ . Dies bedeutet, dass zwei Zahlen genau dann in der gleichen Restklasse sind, wenn ihre Differenz ein Vielfaches des Moduls $n$ 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 $a$ durch $n$ . Alternativ kann man es auch so sehen, dass dieser Operator die kleinste Zahl zurückgibt, welche in der Restklasse von $a$ modulo $n$ 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 + 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+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 (\mod 12)$ berechnen, ersetzen wir das Ergebnis durch die kleinste Zahl seiner Restklasse: Aus $11+7=18$ wird $6$ (Uhr). Ebenso können wir auch die Summanden ersetzen, z.B. wenn wir “21 Stunden nach 19 Uhr” bestimmen wollen. Dann wird $19+21 (\mod 12)$ zu $7 + 9 (\mod 12)$ , abschliessend wird das Ergebnis von $16$ zu $4$ (Uhr).

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

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

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

(a+c_1n)(b+c_2n) = ab + ac_2n+c_1bn+ c_1c_2n^2 \equiv ab (\mod n).

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

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 $2^{42'434'546}+1 (\mod 1337)$ . Ein ersten Ansatz wäre, zuerst $2^{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 $2^{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 $2^{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 $2^{42'434'546}+1$ ganze $42'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 $42'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 $2\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 $a$ negativ ist. So ist es in C++ immer negativ und man muss $n$ zum Ergebnis dazuzählen, um das kleinste nicht-negative Mitglied der Restklasse zu erhalten, d.h. man benutzt in diesem Fall a%n+n.