Mathematik: Zahlentheorie: Chinesischer Restsatz

Satz (Chinesischer Restsatz): Sind m und n zueinander teilerfremd, dann ist der Restklassenring Z/mnZ isomorph zum direkten Produkt von Z/mZ und Z/nZ. Anders ausgedrückt: Zu gegebenen ganzen Zahlen a und b gibt es eine ganze Zahl x mit $x\equiv a\mod m$ und $x\equiv b\mod n$, und x ist bis auf Kongruenz modulo m*n eindeutig bestimmt.

Beweis: Nach Kap.2 gibt es ganze Zahlen r,s mit rm+sn=ggT(m,n)=1. Dann löst x=asn+brm beide Kongruenzen. Zur Eindeutigkeit: Sind x und y Lösungen beider Kongruenzen, dann ist x-y durch m sowie durch n teilbar, also auch durch deren kgV, das wegen der Teilerfremdheit gleich ihrem Produkt ist.

Für eine beliebige endliche Anzahl paarweise teilerfremde Zahlen gilt die entsprechende Verallgemeinerung. Dies funktioniert deshalb, weil jede der Zahlen dann auch zum Produkt der übrigen teilerfremd ist.

Beispiel: Die Schüler einer Klasse sollen sich zu Gruppen gleicher Größe ordnen. Sie versuchen zuerst, sich zu Dreiergruppen zusammenzufinden, doch es bleibt ein Schüler übrig. Bei Vierergruppen bleiben 3 Schüler übrig. Bei Fünfergruppen klappt es endlich. Wieviele Schüler sind in der Klasse?

Lösung: Sei x die gesuchte Anzahl. Aus $x\equiv 1\mod 3$ und $x\equiv 3\mod 4$ folgern wir mittels -1*3+1*4=1: $x\equiv 1*4+3*(-1)*3\equiv -5\mod 12$.

Weiter folgt aus $x\equiv 0\mod 5$ mit -2*12+5*5=1:

$x\equiv -5*5*5+0*(-2)*12\equiv -125\equiv -5\equiv 55\mod 60$.

Die Klasse enthält also mindestens 55 Schüler.