## [Chinesischer Restsatz](/de/node/62030) Definition Ein Satz, der besagt, dass ein System simultaner Kongruenzen x ≡ a_i (mod m_i) mit paarweise teilerfremden Moduli m_i eine eindeutige Lösung modulo M = ∏ m_i besitzt; äquivalent ist, dass der Ring Z/MZ isomorph zum Produkt der Z/m_iZ ist, wenn die m_i paarweise teilerfremd sind. ## Prinzip Prinzip Die organisierende Idee ist, dass Teilerfremdheit der Moduli eine Bijektion zwischen Restklassen modulo dem Produkt und Tupeln von Resten modulo jedem einzelnen Modul erzeugt, was unabhängige Festlegung von Resten und konstruktive Rekonstruktion ermöglicht. ## Demonstration Demonstration Beispiel: Löse x ≡ 2 (mod 3) und x ≡ 3 (mod 5). Da 3 und 5 teilerfremd sind, existiert eine eindeutige Lösung modulo 15; man findet x ≡ 8 (mod 15), konstruiert z. B. mit dem Standardalgorithmus unter Verwendung modularer Inversen. ## Fehlanwendung Fehlanwendung Anwendung des Satzes bei nicht paarweise teilerfremden Moduli; dieser Missbrauch kann dazu führen, eine eindeutige Lösung modulo dem Produkt zu behaupten, obwohl keine Lösung oder mehrere Restklassen modulo dem kgV auftreten können. ## Konsequenz Konsequenz Richtige Anwendung liefert eine explizite konstruktive Methode zur Lösung simultaner Kongruenzen, bildet die Grundlage effizienter Algorithmen in der algorithmischen Zahlentheorie und Kryptographie und ermöglicht die Zerlegung modularer Arithmetik in kleinere unabhängige Komponenten. ## Umkehrung Umkehrung Teilen die Moduli nichttriviale ggT, so muss die Kompatibilität geprüft werden und Lösungen sind, falls vorhanden, nur modulo dem kleinsten gemeinsamen Vielfachen eindeutig statt modulo dem Produkt; die einfache Bijektion bricht zusammen. ## Abgrenzung Abgrenzung Geltungsbereich: erfordert paarweise teilerfremde Moduli für die klassische Aussage der Eindeutigkeit modulo dem Produkt. Verallgemeinerungen für nicht teilerfremde Moduli existieren, verlangen jedoch Verträglichkeitsbedingungen; der Satz betrifft Reste modulo ganzer Zahlen und gilt nicht unmittelbar für nichtkommutative Ringe ohne Anpassung. ## Semantische Spannung Semantische Spannung Spannung besteht zwischen der einfachen coprimen Version (Eindeutigkeit modulo Produkt) und der allgemeineren, kompatibilitätsbasierten Version für nicht teilerfremde Moduli; die beiden werden manchmal verwechselt, wobei die Notwendigkeit der Paarweise-Teilerfremdheit vergessen wird. ## Synthese Synthese Der Chinesische Restsatz fasst eine strukturelle Bijektion zusammen: Paarweise teilerfremde Moduli erlauben das Kodieren globaler Reste als unabhängige lokale Reste und die Rekonstruktion einer eindeutigen globalen Lösung modulo dem Produkt, was sowohl theoretische Zerlegung als auch ein praktisches konstruktives Verfahren bietet.