Der chinesische Restsatz erklärt

Eine Zahl lässt bei Division durch 3 den Rest 2, durch 5 den Rest 3 und durch 7 den Rest 2. Welche Zahl ist es? Probiert man die Zahlen der Reihe nach, kommt man nach einer Weile auf 23, aber in der Frage steckt ein Satz: Solange die Teiler keinen gemeinsamen Faktor haben, gibt es unterhalb ihres Produkts immer genau eine Antwort, und man findet sie, ohne etwas auszuprobieren. Der Satz ist etwa 1.500 Jahre alt und arbeitet noch heute in Kalendern, in der Computerarithmetik und in der Kryptografie, die das Web schützt.

Drei Reihen von Markierungen für die Zahlen mit Rest 2 mod 3, 3 mod 5 und 2 mod 7, die in einer Spalte bei 23 zusammentreffen
Drei Reihen von Markierungen für die Zahlen mit Rest 2 mod 3, 3 mod 5 und 2 mod 7, die in einer Spalte bei 23 zusammentreffen

Eine Aufgabe aus dem Sunzi Suanjing

Das Sunzi Suanjing, ein chinesisches Rechenbuch aus dem 3. bis 5. Jahrhundert, fragt nach einer Anzahl Dinge, die zu dritt gezählt 2 übrig lässt, zu fünft 3 und zu siebt 2. Seine Antwort ist 23, und sein Verfahren wird noch heute gelehrt: Nimm 70 für jedes Ding, das beim Zählen zu dritt übrig bleibt, 21 für jedes beim Zählen zu fünft und 15 für jedes beim Zählen zu siebt, addiere und ziehe 105 so oft ab, wie es geht. 2 × 70 + 3 × 21 + 2 × 15 = 233, und 233 − 2 × 105 = 23. Ein Vers aus der Ming-Zeit hielt die Zahlen 70, 21, 15 und 105 jahrhundertelang im Gedächtnis. Qin Jiushao gab 1247 ein allgemeines Verfahren an, dieselbe Aufgabe steht in Fibonaccis Liber Abaci von 1202, und Carl Friedrich Gauß formulierte den Satz 1801 in seinen Disquisitiones Arithmeticae in seiner heutigen Form.

Eine Seite einer Qing-Ausgabe des Sunzi Suanjing, des chinesischen Rechenbuchs vom 3. bis 5. Jahrhundert, das nach einer Zahl fragt, die beim Zählen in Dreier-, Fünfer- und Siebenergruppen 2, 3 und 2 übrig lässt.
Eine Seite einer Qing-Ausgabe des Sunzi Suanjing, des chinesischen Rechenbuchs vom 3. bis 5. Jahrhundert, das nach einer Zahl fragt, die beim Zählen in Dreier-, Fünfer- und Siebenergruppen 2, 3 und 2 übrig lässt.
Carl Friedrich Gauß auf einem Porträt von Christian Albrecht Jensen aus dem Jahr 1840. Die Kongruenzschreibweise a ≡ b (mod n) führte er in den Disquisitiones Arithmeticae von 1801 ein.
Carl Friedrich Gauß auf einem Porträt von Christian Albrecht Jensen aus dem Jahr 1840. Die Kongruenzschreibweise a ≡ b (mod n) führte er in den Disquisitiones Arithmeticae von 1801 ein.

Was der Satz besagt

Nimm Moduln n₁, n₂, …, nₖ, von denen keine zwei einen gemeinsamen Teiler haben, und beliebige Reste a₁, a₂, …, aₖ. Dann gibt es genau eine ganze Zahl x von 0 bis N − 1, mit N = n₁ × n₂ × … × nₖ, die bei Division durch nᵢ für jedes i den Rest aᵢ lässt. Alle anderen Lösungen unterscheiden sich davon um ein Vielfaches von N. In der Schreibweise der modularen Arithmetik: Das System x ≡ aᵢ (mod nᵢ) hat eine Lösung, und sie ist eindeutig mod N. Anders gesagt tragen eine Zahl von 0 bis N − 1 und die Liste ihrer Reste genau dieselbe Information: 3 × 5 × 7 = 105 Zahlen und 3 × 5 × 7 = 105 mögliche Restlisten, jede genau einmal verwendet.

Die Lösung bauen

Die Zahlen 70, 21 und 15 sind keine Zauberei. Jede lässt bei Division durch ihren eigenen Modul den Rest 1 und bei Division durch die anderen den Rest 0: 70 = 2 × 35 ist ein Vielfaches von 5 und 7 und lässt bei Division durch 3 den Rest 1. Allgemein nimmt man Nᵢ = N / nᵢ, ein Vielfaches jedes Moduls außer nᵢ, und multipliziert es mit yᵢ, dem Inversen von Nᵢ mod nᵢ. Das Inverse existiert, weil Nᵢ und nᵢ keinen gemeinsamen Teiler haben, und der erweiterte euklidische Algorithmus findet es: Er führt Euklids Divisionen für den größten gemeinsamen Teiler aus und rechnet zurück bis zum Lemma von Bézout 1 = s × nᵢ + t × Nᵢ, sodass t das Inverse ist. Dann passt x = a₁N₁y₁ + a₂N₂y₂ + …, reduziert mod N, zu jeder Gleichung, weil jeder Term zu seiner eigenen Gleichung passt und in allen anderen verschwindet.

Gleichung für Gleichung

Es gibt einen zweiten Weg, der kein Produkt aller Moduln braucht. Jede Lösung von x ≡ 2 (mod 3) hat die Form x = 2 + 3t. Setzt man das in die nächste Gleichung ein, erhält man 2 + 3t ≡ 3 (mod 5), also 3t ≡ 1 (mod 5), und die Multiplikation mit 2, dem Inversen von 3 mod 5, ergibt t ≡ 2 (mod 5). Dann ist x = 2 + 3 × 2 = 8, und die ersten beiden Gleichungen zusammen besagen x ≡ 8 (mod 15). Wiederholt man das mit der dritten Gleichung, ergibt 8 + 15t ≡ 2 (mod 7) t ≡ 1, also x ≡ 23 (mod 105). Dieses Einsetzen hält die Zahlen kleiner, ist die Art, wie ein Computer solche Systeme meist löst, und funktioniert auch, wenn die Moduln einen gemeinsamen Teiler haben.

Moduln mit gemeinsamem Teiler

Haben zwei Moduln einen gemeinsamen Teiler, überschneiden sich ihre Gleichungen: x ≡ 1 (mod 4) sagt bereits, dass x ungerade ist, und x ≡ 4 (mod 6) sagt, dass x gerade ist, also erfüllt kein x beide. Allgemein können x ≡ a (mod m) und x ≡ b (mod n) genau dann zugleich gelten, wenn a und b bei Division durch g = gcd(m, n) denselben Rest lassen, also wenn g die Differenz a − b teilt. Dann ist die Lösung eindeutig mod lcm(m, n) = m × n / g, nicht mod m × n. Das alte Rätsel vom Eierkorb, dessen Eier zu 2, 3, 4, 5 oder 6 herausgenommen 1 übrig lassen und zu 7 herausgenommen keines, hat die Antwort 301, die sich alle 420 = lcm(2, 3, 4, 5, 6, 7) wiederholt. Ein System hat genau dann eine Lösung, wenn je zwei seiner Gleichungen zusammenpassen, also enthält ein unlösbares System immer ein Paar, das sich widerspricht.

Kalender, Computer und RSA

1583 verband Joseph Scaliger drei Kalenderzyklen, den 28-jährigen Sonnenzirkel, den 19-jährigen Mondzirkel und die 15-jährige Indiktion, zur Julianischen Periode von 28 × 19 × 15 = 7.980 Jahren. Nach dem Satz hat jedes Jahr seine eigene Kombination der drei Zyklusnummern, und die Periode beginnt 4713 v. Chr., im letzten Jahr, in dem alle drei 1 waren; Astronomen zählen noch heute Julianische Tage von dort an. Computer nutzen den Satz, um mit riesigen Zahlen als Listen kleiner Reste zu rechnen, die man getrennt und parallel addieren und multiplizieren und am Ende zusammenfügen kann. Die RSA-Entschlüsselung funktioniert genauso: c^d mod n mit n = p × q wird als zwei Potenzen mod p und mod q berechnet und mit dem Satz zusammengefügt, etwa viermal schneller als eine Potenz mod n. Verfahren zur Geheimnisteilung, etwa die von Mignotte und von Asmuth und Bloom, verstecken ein Geheimnis in Resten, sodass erst genügend davon zusammen es preisgeben.

Ron Rivest, Adi Shamir und Len Adleman (von links nach rechts)
Ron Rivest, Adi Shamir und Len Adleman (von links nach rechts)

Selbst ausprobieren

Öffnen Sie den Rechner, um ein beliebiges Kongruenzsystem einzugeben, mit bis zu 20 Gleichungen und Zahlen mit bis zu 200 Stellen, oder wählen Sie eines der Rechenbeispiele: Sunzis Aufgabe, den Eierkorb, die Julianische Periode, zwei Busfahrpläne, die RSA-Entschlüsselung und ein System ohne Lösung. Der Rechenweg steht mit Ihren Zahlen da, über die Konstruktion oder über Einsetzen, mit dem erweiterten euklidischen Algorithmus für jedes Inverse. Das Bild markiert die Zahlen, die jede Gleichung erfüllen, sodass Sie die eine Spalte sehen, in der sich alle treffen, oder legt die Reste zweier Gleichungen in einer Tabelle aus, in der jede Zahl ihre eigene Zelle hat.

Häufig gestellte Fragen

Ist die Lösung eines Kongruenzsystems eindeutig?

Nur bis auf ein Vielfaches des Moduls. Wenn x = 23 Sunzis Aufgabe löst, dann auch 23 + 105 = 128, 233 und −82, denn das Addieren von 105 ändert keinen der Reste. Der Satz besagt, dass es genau eine Lösung von 0 bis 104 gibt; bei Moduln mit gemeinsamen Teilern genau eine unterhalb ihres kleinsten gemeinsamen Vielfachen.

Warum müssen die Moduln teilerfremd sein?

Für die Konstruktion, weil Nᵢ ein Inverses mod nᵢ haben muss, und das gibt es nur, wenn sie keinen gemeinsamen Teiler haben. Für den Satz selbst, weil gemeinsame Teiler manche Gleichungen überlappen lassen: Dann hat ein System entweder keine Lösung oder weniger verschiedene, und die Lösungen wiederholen sich alle kleinsten gemeinsamen Vielfachen statt alle Produkte.

Wie finde ich ein modulares Inverses von Hand?

Mit dem erweiterten euklidischen Algorithmus. Für das Inverse von 15 mod 7: 15 = 2 × 7 + 1, also 1 = 15 − 2 × 7, und 15 × 1 ≡ 1 (mod 7): Das Inverse ist 1. Für 35 mod 3: 35 = 11 × 3 + 2 und 3 = 1 × 2 + 1, also 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, und das Inverse von 35 mod 3 ist −1 ≡ 2. Bei kleinen Moduln kann man auch einfach 1, 2, 3, … probieren, bis das Produkt den Rest 1 lässt.

Was hat der Satz mit Uhren zu tun?

Ein Rest mod n ist eine Position auf einer Uhr mit n Stunden. Zwei Uhren mit 3 und 5 Stunden, die gemeinsam starten und jeweils um eine Stunde weiterrücken, zeigen jedes der 15 Positionspaare genau einmal, bevor sie wieder am Anfang stehen, weil 3 und 5 keinen gemeinsamen Teiler haben. Uhren mit 4 und 6 Stunden sind nach 12 Schritten zurück und zeigen nur 12 der 24 Paare: Positionen mit einer ungeraden und einer geraden Zahl treten nie zusammen auf.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Rechner für den chinesischen Restsatz öffnen