Chinesischer Restsatz
Simultane Kongruenzen ganzer Zahlen
Die Originalform des Satzes aus einem Buch des chinesischen Mathematikers Ch'in Chiu-Shao aus dem Jahr 1247 ist eine Aussage über simultane Kongruenzen. Seien n1, ..., nk positive ganze paarweise teilerfremde Zahlen. Dann existiert für alle gegebenen Ganzzahlen a1, ..., ak eine Ganzzahl x, die das Kongruenzensystem
- x ≡ ai mod ni für i = 1...k (1)
löst.
Weiterhin sind alle Lösungen x dieses Systems kongruent modulo dem Produkt n = n1...nk.
Eine Lösung x kann folgendermaßen gefunden werden. Für jedes i sind die Ganzzahlen ni und n/ni teilerfremd, und mit dem erweiterten Euklidischen Algorithmus lassen sich Ganzzahlen r und s finden, so dass r ni + s n/ni = 1. Wenn wir ei = s n/nisetzen, haben wir
- ei ≡ 1 mod ni und ei ≡ 0 mod nj für j ≠ i.
Die Zahl x = ∑i=1..k ai ei löst das Kongruenzensystem (1).