Chinesischer Restsatz

Simultane Kongruenzen ganzer Zahlen

Eine simultane Kongruenz ist ein System von linearen Kongruenzen

${\begin{matrix}x&\equiv &a_{1}&\mod m_{1}\\x&\equiv &a_{2}&\mod m_{2}\\&\vdots &&\\x&\equiv &a_{n}&\mod m_{n}\\\end{matrix}}$

für die alle x bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Es kann aber auch keine Lösung geben.

Die Originalform des Chinesischen Restsatzes aus einem Buch des chinesischen Mathematikers Ch'in Chiu-Shao aus dem Jahr 1247 lautet:

Seien m₁, ..., m_n paarweise teilerfremde positive ganze Zahlen, dann existiert für alle gegebenen ganzen Zahlen a₁, ..., a_n genau eine x modulo m₁m₂m₃...m_n, das die obige simultane Kongruenz erfüllt.

Finden einer Lösung

$\mathrm {Sei} \ M=m_{1}m_{2}m_{3}\dots {}m_{n}\ \mathrm {und} \ M_{i}={\frac {M}{m_{i}}},\quad 1\leq i\leq n$

Für jedes i ist die Ganzzahlen n_i und M_i teilerfremd, daher gibt es auch stets ein y_i, sodass gilt:

$M_{i}\cdot {}y_{i}\equiv 1\mod m_{i}$

Diese Kongruenz lässt sich lösen (siehe lineare Kongruenz). Das gesuchte x ist nun:

$x\equiv {}\sum _{i=1}^{n}a_{i}M_{i}y_{i}\mod M$