Der chinesische Restsatz
Motivation
Als Motivation gelte einmal folgendes Beispiel: Ich habe Bonbons. Wenn ich diese Bonbons an
Personen verteile, bleiben
Bonbons übrig. Wenn ich sie an
Personen verteile, bleiben
Bonbons übrig. Wie viele Bonbons habe ich?
Es gilt:
-
mod
-
mod
Wie gehe ich vor? Ich habe einen "Trick". :-) ... Ich suche zunächst die Inversen der Moduln zueinander, also
-
mod
-
mod
(Diese existieren, weil beide Moduln teilerfremd sind). Wir kommen (in diesem einfachen Fall mit ein bisschen überlegen) auf
-
-
.
Und jetzt rechne ich... moooment... . Ja, genau.
Bonbons hab ich, ne? (oder 94... oder 122... oder 150... mmmh... oder 38... oder 10... :-)).
Verallgemeinerung auf zwei Moduln
Seien und
teilerfremd. Zu lösen sei das Kongruenzsystem:
-
mod
-
mod
Man bestimmt Zahlen und
folgendermaßen:
-
mod
-
mod
Dann ist eine Lösung , denn
-
mod
-
mod
Weitere Lösungen ergeben sich durch (für
)
So, und jetzt richtig allgemein: Der chinesische Restsatz
Die Zahlen seien paarweise teilerfremd. Dann besitzt das Kongruenzsystem
-
mod
- ...
-
mod
eine Lösung mod und alle Lösungen liegen in derselben Kongruenzklasse modulo
.
Beweis: