Der chinesische Restsatz hat viele Anwendungen, etwa bei der Jordanschen Normalform, beim Lösen von simultanen Kongruenzen und bei der Interpolation von Polynomen. Er ist in vielen Formen bekannt, sodass es sich lohnt, zunächst allgemeinere Untersu\- chungen durchzuführen. \red ^0 \black
Nun gelte umgekehrt (\alpha_1 \cut ... \cut \alpha_i) ° \alpha_(i+1)=M \cross M für jedes i \in menge(1, ... ,n-1). Für i \in menge(1, ..., n-1) definiere eine Abbildung g_i von M auf M\/\alpha_1 \cross ... \cross M\/\alpha_i durch
g_i(x)=(\alpha_1(x), ...,\alpha_i(x))
Dann ist sicher g_1 surjektiv. Es sei i \in menge(1, ..., n-1) und g_i surjektiv. Wir behaupten, dass dann auch g_(i+1) surjektiv ist, sodass wegen g_n=f auch f surjektiv ist: Seien m_1, ..., m_(i+1) \in M beliebig. Es gibt ein x \in M mit g_i(x)=(\alpha_1(m_1), ..., \alpha_i(m_i)). Dann ist
womit es ein y \in M derart gibt, dass für jedes k \in menge(1, ..., i) (x,y) \in \alpha_k und (y,m_(i+1)) \in \alpha_(i+1) gilt. Ist k \in menge(1, ..., i), so ist (x,m_k) \in \alpha_k wegen g_i(x)=(\alpha_1(m_1), ..., \alpha_i(m_i)) sowie (y,x) \in \alpha_k, also auch (y,m_k) \in \alpha_k. Wegen (y,m_(i+1)) \in \alpha_(i+1) ist daher y ein Urbild von (\alpha(m_1), ..., \alpha(m_(i+1))). \bigbox
Kommen wir nun zu den wichtigsten Anwendungsgebieten des chinesischen Restsatzes, den Ringen.
array(Satz 2)__: Es seien R ein Ring mit 1 und I, J Ideale von R. Definiere die Äquivalenzrelation \alpha_I auf R durch
(x,y) \in \alpha_I <=> x-y \in I
und entsprechend \alpha_J \(d.h. R \/ \alpha_I = R \/ I). Dann ist
I+J=R <=> \alpha_I ° \alpha_J=R \cross R
Beweis__: Sei zunächst I+J=R. Es gibt dann ein (i,j) \in I \cross J mit 1=i+j. Sei (x,y) \in R \cross R beliebig. Für z:=xj+yi gilt dann
x-z=x(1-j)-yi=(x-y)i \in I z-y=xj-y(1-i)=(x-y)j \in J
also (x,z) \in \alpha_I, (z,y) \in \alpha_J, d.h. (x,y) \in \alpha_I ° \alpha_J. Sei umgekehrt \alpha_I ° \alpha_J=R \cross R und x\in\R beliebig. Dann ist (x,0)\in\alpha_I ° \alpha_J, womit es ein y \in R mit (x,y) \in \alpha_I und (y,0) \in \alpha_J, d.h. x-y\in\ I und y\in\ J gibt. Dann ist x=(x-y)+y \in I+J und folglich R=I+J. \bigbox
Die Beweisidee zeigt, dass es egal ist, ob I, J jeweils nur Links\- oder Rechtsideale sind.
Seien I_1, ..., I_n Ideale des Ringes R. Dann definieren wir ihr Produkt I_1 ... I_n durch die Menge aller sum(((a_1))_i ... ((a_n))_i,i=1,k), wobei k\in\IN und für alle j\in menge(1, ..., n) a_j eine Abbildung von menge(1, ..., k) nach I_j ist. Aufgrund der Idealeigenschaften gilt I_1 ... I_n \subseteq I_1 \cut ...\cut I_n.
array(Satz 3)__: Es seien R ein Ring mit 1 und I_1, ..., I_n, J Ideale von R. Gilt I_k+J=R für jedes k \in menge(1, ..., n), so gilt
I_1 ... I_n+J=I_1 \cut ...\cut I_n+J=R.
Beweis__: Wegen I_1 ... I_n \subseteq I_1 \cut ... \cut I_n brauchen wir nur
I_1 ... I_n+J=R
zu zeigen. Nach Voraussetzung gilt I_1+J=R. Ist nun I_1 ... I_k+J=R für k \in menge(1, ..., n-1), so gibt es ein x \in I_1 ... I_k und ein a \in J mit 1=x+a. Nach Voraussetzung gibt es ferner ein y \in I_(k+1) und ein b \in J mit 1=y+b. Daraus folgt
1=(x+a)(y+b)=xy+ay+xb+ab \in I_1 ... I_n+J
und damit I_1 ... I_(k+1)+J=R, bis zur Behauptung I_1 ... I_n+J=R. \bigbox
Nun kommt endlich der
\big\Chinesische Restsatz\normal\ : Es seien R ein Ring mit 1 und I_1, ..., I_n Ideale von R. Für die durch f(x) := (x+I_1, ..., x+I_n) definierte Abbildung von R nach R\/I_1 \cross ... \cross R\/I_n gilt:
a\) Kern(f)=I_1 \cut ... \cut I_n
b\) Genau dann gilt I_i+I_j=R für alle i, j \in menge(1, ..., n) mit i != j, wenn f surjektiv ist.
c\) Falls R kommutativ und f surjektiv ist, gilt I_1 \cut ... \cut I_n = I_1 ... I_n .
Beweis__: Dass f ein Homomorphismus mit dem Kern von a\) ist, ist klar.
b\): Es sei f surjektiv. Für i != j definieren wir eine Abbildung g durch
g(x)=(x+I_i, x+I_j)
Sie ist wegen f auch surjektiv, sodass
\alpha_(I_i) ° \alpha_(I_j) = R \cross R
mit Satz 1 folgt. Satz 2 ergibt dann I_i+I_j=R.
Nun gelte umgekehrt I_i+I_j=R für i != j. Mit Satz 3 folgt daraus
(I_1 \cut ... \cut I_i)+I_(i+1)=R
Wendet man Satz 2 und anschließend Satz 1 an, so folgt die Surjektivität von f.
c\) erledigen wir per Induktion nach n. Der Induktionsanfang ist klar. Nun sei R kommutativ und f surjektiv und es gelte die Behauptung für n-1. Mit J:=I_1 \cut ... \cut I_(n-1) und Satz 3 folgt damit
Seien R ein euklidischer Ring und p_1, ..., p_n paarweise teilerfremde Elemente von R. Dann gilt p_i R + p_j R = R für i != j, sodass die im chinesischen Restsatz definierte Abbildung surjektiv ist. Weil euklidische Ringe kommutativ sind, ist der Kern dieser Abbildung
p_1 R \cut ... \cut p_n R = p_1 R ... p_n R = ... = (p_1 ... p_n) R
Mit dem ersten Isomorphiesatz folgt daher
R \/ p_1 R \cross ... \cross R \/ p_n R ~= R \/ (p_1 ... p_n)R
Insbesondere ist \IZ_(p_1) \cross ... \cross \IZ_(p_n) für paarweise teilerfremde p_i \in \IZ zyklisch.
array(Systeme simultaner linearer Kongruenzen)__
Ein System simultaner linearer Kongruenzen besteht in einem Ring aus endlich vielen Gleichungen der Form
x == b_i mod m_i
Ist nun R ein euklidischer Ring, wobei ein wichtiges Beispiel dafür \IZ ist, und sind die m_i paarweise teilerfremd, so ist wieder die Abbildung aus dem chinesischen Restsatz surjektiv, womit insbsondere
(b_1+m_1 R, ..., b_n+m_n R)
ein Urbild x \in R hat. Dieses x löst dann das obige System. Diese Lösung ist aufgrund des Kerns der Abbildung modulo m_1, ..., m_n sowie modulo m_1 ... m_n eindeutig bestimmt, sodass wir nur dieses x brauchen, um die gesamte Lösungsmenge des Systems angeben zu können. Es gibt sogar einen Algorithmus, der dieses x ermittelt:
Die Umgebung ist ein euklidischer Ring R mit seiner Arithmetik, insbesondere einer Gradfunktion \delta und Operatoren DIV und MOD mit
a = (a DIV b)b + a MOD b
und a MOD b=0 oder \delta(a MOD b) < \delta(b) für alle a \in R, b \in R-menge(0). Ferner seien b_1, ..., b_n \in R und paarweise teilerfremde m_1, ..., m_n \in R gegeben. Der folgende \big Algorithmus Chinese \normal\ liefert dann ein x \in R mit x ==b_i mod m_i für alle i \in menge(1, ..., n):
\ref(1) w_1 := b_1 \ref(2) for k=2 to n do \ref(3) | Algorithmus Lagrange \red ^1 \black liefert ein \small y\in\R mit ym_1\....m_(k-1)==array(1 mod m_k) \ref(4) | w_k := w_(k-1)+((b_k-w_(k-1))y MOD m_k) m_1 ... m_(k-1) \ref(5) end \ref(6) x := w_n
Um diesen Algorithmus zu verifizieren, zeigen wir zunächst, dass Zeile 3 überhaupt gerechtfertigt ist, d.h. dass m_1 ... m_(k-1) und m_k teilerfremd sind. Es gibt ja x_i, y_i \in R mit x_i m_i + y_i m_k=1 für i < k. Multiplikation dieser k\-1 Gleichungen ergibt
Bei den restlichen Summanden können wir m_k ausklammern. Es folgt
1=(x_1 ... x_(k-1))(m_1 ... m_(k-1))+z m_k
für ein z \in R, sodass in der Tat m_1 ... m_(k-1) und m_k teilerfremd sind.
Wir müssen ja w_n == b_i mod m_i für alle i \in menge(1, ..., n) zeigen. Es gilt aber noch mehr, nämlich w_k == b_i mod m_i für i \in menge(1, ..., k) \red ^2 \black . Das zeigen wir per Induktion nach k. Der Induktionsanfang ist mit Zeile 1 klar. Nun sei i \in menge(1, ..., k) und die Aussage für k\-1 wahr. Für i w_k == w_(k-1) == b_i mod m_i
Damit ist der Algorithmus Chinese verifiziert. | | | | | | | | | | | | | \bigbox
Ein kleines Beispiel im euklidischen Ring \IZ: Das System
x == 1 mod 4 x == 2 mod 5 x == 3 mod 7
lösen wir mit dem Algorithmus Chinese:
Bei k=2 erfüllt (y', y)=(1, -1) die Gleichung y' m_k+y m_1 ... m_(k-1)=1, womit w_2=1+(-1 MOD 5)4=17 ist. Bei k=3 erfüllt (y', y)=(3, -1) jene Gleichung, womit x=w_3=17+(14 MOD 7)20=17 ist.
Wegen m_1 m_2 m_3 = 4*5*7=140 lautet die Lösungsmenge also
menge(x \in \IZ | x == 17 mod 4*5*7)=menge(x \in \IZ | 140 teilt x-17)
Interpolation__
Hier werden wir sehen, dass sich die Polynominterpolation auf den chine\- sischen Restsatz und damit sich die Bestimmung des Interpolationspolynoms auf den Algorithmus Chinese zurückführen lässt.
Es sei K ein (kommutativer) Körper und a_0, ..., a_n paarweise verschiedene Elemente von K sowie b_0, ..., b_n \in K. Es gibt dann genau ein f \in K[x] mit folgenden Eigenschaften:
\ref(1) Für i \in menge(0, ..., ) ist f(a_i)=b_i . \ref(2) Es ist f=0 oder Grad(f) <= n.
Beweis__: Setze p_i = x-a_i. Dann ist p_i(a_i)=0 und die p_i sind paarweise teilerfremd, womit es nach vorigem Abschnitt über Kongruenzen ein f \in K[x] mit f == b_i mod p_i gibt, simultan für alle i \in menge(0, ..., n). Der Rest g bei der Division von f durch p_0 ... p_n erfüllt ebenfalls diese Kongruenz sowie 2) wegen Grad(p_0 ... p_n)=n. Ferner gibt es Polynome q_i mit
g=b_i+q_i p_i
sodass g(a_i)=b_i+q_i(a_i)p(a_i)=b_i ist, also 1\) durch g erfüllt ist. Die Eindeutigkeit folgt aus der Eindeutigkeit des Restes in K[x]. \bigbox
Zum Schluss noch drei Links zur Motivation dieses Artikels: Link 1 Link 2 Link 3
0 Diesen Artikel gibt es auch im pdf-Format. 1 Siehe HIER. 2 Das bedeutet, dass wir noch während des Lösens eines Systems simultaner linearer Kongruenzen beliebig viele Gleichungen hinzufügen können.
...hat viele Anwendungen, etwa bei der Jordan'schen Normalform, beim Lösen von simultanen Kongruenzen und bei der Interpolation von Polynomen. Er ist in vielen Formen bekannt, sodass es sich lohnt, zunächst allgemeinere Untersu chungen durchzuführen.
ich honoriere Deine Leistung schon, aber ich hätte mir mehr gewünscht, dass Du den Satz mit den Themen verknüpfst, die Du in der Einleitung beschrieben hast. Es ist immer schön zu sehen, dass die "trockene" Materie einen "angewandten" Nutzen hat.
Versteh mich bitte nicht falsch, natürlich muss die Theorie als Grundlage für Praxis zuerst bereitet werden, aber die trockene Theorie kann ich auch in Skripten nachlesen.
Freue mich schon auf Deinen nächsten Artikel!
Ich habe von drei Anwendungen gesprochen. Und zwei davon, nämlich simultane Kongruenzen und Polynominterpolation, habe ich doch behandelt, oder nicht? Und in den drei angegebenen Links findet man ja noch weitere.
Du schreibst
aber die trockene Theorie kann ich auch in Skripten nachlesen.
Ich habe kein ausführliches Skript zum Thema gefunden.
ich kann das irgendwie schlecht in Worte fassen....
Vielleicht liegt es auch an mir, dass ich was anderes erwartet habe.
Leider weiss ich selbst nicht genau was?!
Du hast soviele gute Artikel geschrieben, dass ich mir hier auch etwas anderes vorgestellt habe.
Das ist vielleicht mit einem heissersehnten Fussballspiel zu vergleichen 😄 dass dann doch nur eher dürftig unentschieden ausgeht. 😄
Naja nix für ungut. Auf seine Art ist der Artikel trotzdem beeindruckend, habe vielleicht nur andere Vorstellungen gehabt.
\(\begingroup\)Hi Leute,
habe auch wenig zu dem Thema im Internet gefunden, und freue mich auf den Artikel, den unser Dozent als Übungsaufgabe genannt hat, zumindest Teile davon. Ist eine allgemeine Darstellung des Satzes auch ohne Äquivalenzrelation darstellbar?
Ich habe jetzt schon ein wenig gelesen und habe mit der Notation Probleme. \alpha_1(x) meint sicherlich die Klasse von x bezüglich \alpha.
Unter dem Kern einer Abbildung habe ich immer all jene Elemente verstanden, die auf das neutrale Element des Bildes "zeigen". Hier haben wir aber gar keine Operation auf M definiert. Desweiteren habe ich mit dem Schnitt der Äquivalenzrelationen ein Problem. Mengentheoretisch ist ja ein Relation eine Teilmenge von M \times M, Der Schnitt von Relationen ist nun auch eine Teilmenge von M \times M, aber die Quelle(Definitionsbereich) von f ist M und damit ungleich einer beleibigen Teilmenge von M \times M.
Wahrscheinlich habt ihr einfach nur eine andere Schreibweise, vielleicht könnte jemand einen Ergänzenden Hinweis geben, der mir den Artikel verständlich macht.
tschau Tillmann\(\endgroup\)
\(\begingroup\)Hi Tillmann,
der Kern einer Abbildung f : X -> Y ist die Äquivalenzrelation auf X, die durch
x kern(f) x' <=> f(x) = f(x')
definiert ist. Hier steht das wichtigste dazu.
Gruß
Martin\(\endgroup\)
\(\begingroup\)Nach dem Beweis von Satz 3 und direkt hinter den Anwendungen da ist ein Teil des Artikels den man nicht sehen kann. Ich kann es auch nicht öffnen. Kann mir jemand erklären warum das so ist? Brauche ich vielleicht irgendein update oder so?\(\endgroup\)
\(\begingroup\)Hi zive!
Mit einem Mausklick auf den leeren Bereich kommst Du vorläufig zumindest zum Quelltext des nicht dargestellten Teils.
An einer Behebung des Schadens arbeite ich.
EDIT: Eine Änderung ist in die Wege geleitet. Die Änderung ist nun durchgeführt.
Liebe Grüße, Franz\(\endgroup\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
