Chinesischer Restsatz

In der Zahlentheorie besagt der chinesische Restsatz, dass, wenn man die Reste der euklidischen Division einer ganzen Zahl n durch mehrere ganze Zahlen kennt, man den Rest der Division von n durch das Produkt dieser ganzen Zahlen eindeutig bestimmen kann, unter der Bedingung, dass die Teiler sind paarweise teilerfremd.

Teilerfremd bedeutet, dass es keine natürliche Zahl außer der Eins gibt, die beide Zahlen teilt.

Beispiele:

Eingabe: Divisor = {3, 4, 5}, Rest = {2, 3, 1}

Resultat: 11

11 ist leinste mögliche Dividend, denn:

(1) Wenn wir 11 durch 3 dividieren, erhalten wir 3 und den Rest 2.
(2) Wenn wir 11 durch 4 dividieren, erhalten wir 2 und den Rest 3.
(3) Wenn wir 11 durch 5 dividieren, erhalten wir 2 und den Rest 1.

2. Beispiel

Eingabe: Divisor = {5, 7}, Rest = {1, 3}

Resultat: 31

31 ist der kleinste mögliche Dividend, denn:

(1) Wenn wir 31 durch 5 dividieren, erhalten wir 6 und den Rest 1.
(2) Wenn wir 31 durch 7 dividieren, erhalten wir 4 und den Rest 3.