We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Der chinesische Restsatz Teil 1

00:00

Formale Metadaten

Titel
Der chinesische Restsatz Teil 1
Serientitel
Teil
1
Anzahl der Teile
4
Autor
Lizenz
CC-Namensnennung 3.0 Unported:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
Vorlesung von Prof. Christian Spannagel an der PH Heidelberg.
Lösung <Mathematik>ZahlenbereichModulVerallgemeinerungRechnenZahlKongruenzInhalt <Mathematik>ZehnInverseChinesischer RestsatzBimodulLineares GleichungssystemVorlesung/Konferenz
Weg <Topologie>ZahlEinfach zusammenhängender RaumRechnenVariableModulInverseBimodulSummeVorlesung/Konferenz
Computeranimation
Transkript: Deutsch(automatisch erzeugt)
Okay, folgendes Problem, ich habe eine Tüte mit Gummibärchen, ja, x Gummibärchen sind da drin.
So, wenn ich die Gummibärchen an vier Leute verteile, gleichmäßig, ne, vier Leute gleichmäßig verteile, bleiben zwei Gummibärchen übrig. Wenn ich dieselbe Anzahl Gummibärchen auf sieben Leute verteile, bleiben drei übrig. Wie viele Gummibärchen habe ich? Bitte?
Zehn, nicht schlecht. Zehn. Vielleicht habe ich noch eine andere Zahl? Gingen auch andere Zahlen? Also wenn ich, nimm mal das Beispiel, wenn ich zehn Gummibärchen habe, also wenn ich es auf vier Leute verteile, bleiben zwei übrig, wenn ich es auf sieben verteile, drei.
Okay, prima zehn. Gibt es auch andere Möglichkeiten? Bitte? 100? Wer hat 100 gesagt? 100? Wenn ich 100 auf vier Leute verteile, geht es auf, ne?
102 vielleicht? 38, genau, ne? Richtig. 38 durch 4 bleibt Rest 2 und durch 7 bleibt Rest 3. Genau. Gibt es noch andere? Also ich könnte zehn haben oder 38. Gibt es noch mehr? Naja, okay. Es gibt unendlich viele, ja?
Die Frage ist, wie findet man die? Und auch wie findet man Lösungen für solche und ähnliche Probleme in schwierigeren Fällen, wo man es nicht direkt überblickt? So. Und das verweist auf den chinesischen Restsatz. So. Alles sehr auffühlend heute, ne? Große Satz von Fermat. Okay.
Nehmen wir nochmal das Beispiel. Machen wir es erstmal ganz einfach an dem Beispiel und dann nähern wir uns mit einem allgemeinen Verfahren.
Also. Das Beispiel, was ich gerade erwähnt hatte, war das Folgende. Ich habe x Gummibärchen und wenn ich die auf vier Leute verteile, bleiben zwei übrig. Das ist ja nichts anderes, als das so hinzuschreiben, ne? x ist Konkurrenz 2 modulo 4. Da kommt schon die Feuerwehr.
So. Beziehungsweise, wenn ich x modulo 3 rechne, äh Quatsch, wenn ich x modulo 7 rechne, also auf sieben Leute die Gummibärchen verteile, bleiben drei übrig. So. Okay. Ganz allgemein gesprochen habe ich natürlich dann so ein Problem wie x ist Konkurrent a1 modulo m1
und x ist Konkurrent a2 modulo m2 und x ist Konkurrent a3 modulo m3, a4 modulo m4 und so weiter. Und dann wollen sie das x rauskriegen. Das lernen wir heute, wie das geht. Oder sie vielleicht nicht. Okay. So.
Ich verrate Ihnen mal jetzt an diesem einfachen Beispiel mal vorgehen kann. Da gibt es einen Trick letztlich. Und den Trick, den führe ich Ihnen jetzt mal vor und Sie werden wahrscheinlich nicht so ganz verstehen warum.
Aber wir werden uns anhand des Beispiels, anhand der Verallgemeinerung auf zwei und dann anhand der Verallgemeinerung auf n Modulen klar machen warum das so ist. Was mache ich als erstes? Als erstes mache ich mal das folgende. Ich versuche die inverse der Module gegenseitig zu finden.
Also was versuche ich? Ich will wissen. 7 mal x1 ist Konkurrent 1 modulo 4. Und also was ist das inverse von 7 modulo 4? Und hier genauso umgedreht.
Im allgemeinen Fall später, wenn wir n Modulen haben, geht es nicht um die Inversen der jeweils anderen Modulen, sondern das ist ein bisschen komplizierter.
Dann schauen wir uns das an. Aber jetzt in dem einfachen Fall, im Fall wir haben zwei solche Konkurrenzen. Letztlich handelt es sich um ein Konkurrenzsystem ähnlich wie bei linearen Gleichungssystem. Mit zwei Konkurrenzen sucht man die Inversen der Module im jeweils anderen Modul.
So, was ist denn x1? Du kriegst ja fast den Kopf raus. Ja, genau. Was ist denn x2? Ja, 2, genau.
7 ist nicht Konkurrent 1 modulo 4. 14 ist auch nicht Konkurrent 1 modulo 4. 21, ja 21 ist Konkurrent 1 modulo 4.
So einfach kurz durchprobiert. Genauso hier bei der 4. 4 mal 2 ist 8 und 8 ist Konkurrent 1 modulo 7. Also, ich habe jetzt hier nur die Module betrachtet und jeweils die Inverse gesucht. Und jetzt mache ich das folgende. x ist gleich, passen Sie auf. Ich nehme die 2 hier und multipliziere 7 mal 3 dran.
7 mal 3, das Inverse gerade, mal 2. So. Und addiere dazu, dasselbe nochmal, 3 mal 4 mal 2. Was kommt da raus?
2 mal 7 ist 14 oder 6 mal 7 und 6 mal 4. So. Also, 42 plus 6 mal 4 ist 24, 66. Ist das eine Lösung? 66?
66 ist Konkurrent 2 modulo 4. Und 66 ist Konkurrent 3 modulo 7. Ja. 64 ist durch 4 teilbar, also 66 Konkurrent 2 modulo 4.
Und 63 ist durch 7 teilbar, deswegen ist auch 66 Konkurrent 3 modulo 7. Das haben wir eine Lösung gefunden.
Ohne ausprobieren, ohne rumprobieren. Gut, hier haben wir ein bisschen rumprobiert, aber natürlich kann man das auch anders lösen. Ok. Warum funktioniert das? Wenn wir uns die Summe mal betrachten. Wir rechnen jetzt modulo 4. Wir betrachten uns die Summe.
Das hier hinten wird modulo 4 0, weil die 4 da drin steckt. Wenn ich das hier vorne modulo 4 betrachte, habe ich herausgekriegt, 7 mal 3 ist 1.
Konkurrent 1 modulo 4. Das heißt, es bleibt nur die 2 übrig. Der Teil wird 0, der Teil wird 1, also modulo 4 bleibt die 2 übrig. Wenn ich modulo 7 rechne, ist der Teil 0, weil hier die 7 drin steckt. Ich weiß, das hier ist Konkurrent 1 modulo 7, also bleibt die 3 übrig.
Total systematisch. Ein Teil wird 0, der andere ist 1, weil ich die Inversen so ausgesucht habe. Und dann bleibt genau die eine Zahl übrig, die modulo dieses Moduls eben rauskommen soll. Also wenn man es im allgemeinen Fall macht, im allgemeinen Fall jetzt für 2, dann macht man das folgendermaßen.
Ich habe x ist Konkurrent a1 modulo m1 und x ist Konkurrent a2 modulo m2.
Was mache ich zuerst? Ich bestimme x1 und x2 bestimmen, und zwar mit folgenden Konkurrenzen.
M2 mal x1 ist Konkurrent a1 modulo, Entschuldigung, ist Konkurrent 1 modulo m1.
Also, bezüglich modul 1, m1, suche ich das Inverse für m2. M2 mal x1, das suche ich, das habe ich gegeben, das suche ich, das habe ich gegeben, das ist die einzige Unbekannte in der Konkurrenz.
Genauso wie hier, ich suche sozusagen die Zahl für die m2, das Inverse für m2 in m1. Und genauso suche ich das Inverse für m1 bezüglich m2.
Was mache ich anschließend? Ich bilde x folgendermaßen. Ich nehme mein a1 und multipliziere daran m2 mal x1 plus, jetzt nehme ich mein a2 und multipliziere daran m1 mal x2.
So, das ist das, was wir hier gemacht haben.
Ich nehme mein a1, a1 mal m2 mal x1 und a2 mal m1 mal x2. Das ist der zweite Schritt, bestimme x folgendermaßen, fertig.
Wir können auch noch beweisen, warum das so, warum das stimmt. Nur zur Verdeutlichung, das war die Erklärung, die ich gerade eben gebracht habe zum Allgemeinen.