Chinesischer Restsatz

4.3 Chinesischer Restsatz

4.3.1 Hilfssatz für zwei Kongruenzen

Um sich dem Chinesischen Restsatz⁵³ zu nähern, betrachten wir zunächst einen etwas einfacheren Fall, der die grundsätzliche Fragestellung jedoch beinhaltet: Welche natürliche Zahl $z$ erfüllt die folgenden beiden Kongruenzen:

wenn vorausgesetzt wird, daß $n,m > 0$ relativ prim zueinander sind?

Um sie zu beantworten formulieren wir den Ausgangspunkt zuerst einmal entsprechend Restklassenbeziehung 3.2:

Deren Darstellung als

c = b− a= xn − ym

(4.14)

zeigt mit Verweis auf die Form von 4.10, daß es sich um eine lineare diophantische Gleichung handelt. Wegen $gcd(n,m )= 1$ könnte die zugehörige Lösungsformel 4.12 zwar sofort zur Anwendung kommen – naheliegend (da kurz) ist jedoch auch die Anwendung von BéZOUT’s Identität. Denn multipliziert man $gcd(n,m )= αn + βm = 1$ mit $c$ , dann kann aus

c= c(αn + βm )= αnc + βmc

durch Vergleich mit 4.14 sofort abgelesen werden, daß $x = αc$ und $y = − βc$ gelten muß.⁵⁴ Mit der Erkenntnis aus Formel 4.12, daß es sich bei den Lösungen einer linearen diophantischen Gleichungen immer um eine ganze Lösungsmenge handelt, resultiert:⁵⁵

Durch Einsetzen in Formel 4.13 erhält man

und so eine geschlossene Darstellung für die Lösungsmenge.

zk = αbn + βam + kmn

(4.16)

Mit der von den Restklassen bekannten Kongruenz 3.3 für teilerfremde Zahlen:⁵⁶

können wir die Probe machen.

Die Lösungsmenge $z k$ bildet demzufolge eine Restklasse $[z] mn$ .

z≡ αbn + βam (mod mn )

(4.17)

4.3.2 Ein System von Kongruenzen

Nehmen wir jetzt ein ganzes System von Kongruenzen an:

wobei $gcd(m ,m )= 1 i k$ für $i⁄= k$ gelten soll. Wie schon im Fall von zwei Kongruenzen stellt man die Frage, welche Lösung $x$ kongruent zu allen $ai$ modulo $mi$ ist ( $i= 1,...,n$ ). Ohne einen exakten mathematischen Beweis anzutreten, scheint als Schlußfolgerung aus Abschnitt 4.3.1 einleuchtend, daß die Lösung(en) $x$ eine Restklasse modulo $m = ∏nmi$ darstellen [Knu98, CP05].⁵⁷

Bezeichnen wir mit $-- mi$ das Produkt aller Moduli ausgeschlossen $mi$ , also

n ∏ mj n m-= m-= j=1----= m , i mi mi ∏j=1 j j⁄=i

dann gilt wegen der Teilerfremdheit der einzelnen Moduli $-- gcd(mi,mi)= 1$ bzw. mit dem Satz von BéZOUT:⁵⁸

Im Gegensatz dazu verschwindet $αkmk mod mi$ für $i⁄= k$ , denn $mi$ ist als Faktor in $mk$ enthalten. Die Orthogonalität beider Fälle kann mit Hilfe des KRONECKER-Symbols $δik$ ausgedrückt werden: