Prev    Up    Next  

4.3 Chinesischer Restsatz

4.3.1 Hilfssatz für zwei Kongruenzen

Um sich dem Chinesischen Restsatz52 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:

pict

wenn vorausgesetzt wird, daß n und m relativ prim zueinander sind?

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

pict

Deren Darstellung als

c = b− a= xn − ym
(45)

zeigt mit Verweis auf die Form von 41, daß es sich um eine lineare diophantische Gleichung handelt. Wegen gcd(n,m )= 1  könnte die zugehörige Lösungsformel 43 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 45 sofort abgelesen werden, daß x= αc und y= − β c gelten muß.53 Mit der Erkenntnis aus Formel 43, daß es sich bei den Lösungen einer linearen diophantischen Gleichungen immer um eine ganze Lösungsmenge handelt, resultiert:54

pict

Durch Einsetzen in Formel 44 erhält man

pict

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

zk = αbn + βam + kmn
(47)

Mit der von den Restklassen bekannten Kongruenz 23 für teilerfremde Zahlen:55

pict

können wir die Probe machen.

pict

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

z≡ αbn + βam   (mod mn )
(48)

4.3.2 Ein System von Kongruenzen

Nehmen wir jetzt ein ganzes System von Kongruenzen an:

pict

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 [Knu98CP05].56

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:57

pict

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:

                   {
  --                 0    (i⁄= k)
αkmk mod  mi = δik =            .
                     1    (i= k)

Die endgültige Lösungsidee besteht nun darin, für jede Kongruenz i den folgenden Ausdruck zu bilden:

 n                 n
∑  αkakmk mod  mi = ∑ akδik mod mi = ai mod mi ≡ x (mod mi)
k=1                k=1

Wie zu sehen, ist die Summe auf der linken Seite kongruent zu a
 i  modulo m
  i  , was

     n
x ≡ ∑  αkakmk  (mod m )
    k=1
(49)

als finales Ergebnis rechtfertigt.

Für den einfachen Fall n= 2  von Abschnitt 4.3.1 kann man mit m1 = m2  , m2 = m1  sowie

pict

relativ einfach Kongruenz 48 verifizieren.58

x≡ α1a1m1-+ α2a2m2 = α1a1m2 + α2a2m1 = α1a1m2+ β1a2m1  (mod  m1m2)