Chinesischer Restsatz (auch chinesischer Restklassensatz genannt) ist der Name mehrerer ähnlicher Theoreme der abstrakten Algebra und Zahlentheorie. Simultane Kongruenzen ganzer Zahlen [ Bearbeiten | Quelltext bearbeiten] Eine simultane Kongruenz ganzer Zahlen ist ein System von linearen Kongruenzen für die alle bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Wenn eine Lösung existiert, dann sind mit die Zahlen genau alle Lösungen, wobei für das kleinste gemeinsame Vielfache steht. Es kann aber auch sein, dass es gar keine Lösung gibt. Teilerfremde Moduln [ Bearbeiten | Quelltext bearbeiten] Herleitung [ Bearbeiten | Quelltext bearbeiten] Die Originalform des chinesischen Restsatzes stammt aus dem Buch Sūn Zǐ Suànjīng ( chinesisch 孫子算經 / 孙子算经 – "Sun Zis Handbuch der Arithmetik") des Mathematikers Sun Zi (vermutlich 3. Jh. Chinesischer restsatz online rechner. [1] [2]) und wurde 1247 von Qin Jiushaos Shùshū Jiǔzhāng ( 數書九章 / 数书九章 – "Mathematische Abhandlung in neun Kapiteln") wiederveröffentlicht. Der Satz trifft eine Aussage über simultane Kongruenzen für den Fall, dass die Moduln teilerfremd sind.
Alle Lösungen sind dann kongruent modulo dem kleinsten gemeinsamen Vielfachen der. Eine Lösung lässt sich dann durch sukzessive Substitution von Kongruenzen lösen, bis sich eine simultane Kongruenz mit paarweise teilerfremden Moduln ergibt. Chinesischer Restsatz - Chinese Remainder Theorem. Dieses lässt sich dann wie im Beweis des Restsatzes gezeigt lösen. Wie die sukzessive Substitution erfolgt, soll später an einem konkreten Beispiel gezeigt werden. Chinesischer Restsatz Beispiel Zunächst soll allerdings ein Beispiel durchgerechnet werden, bei dem die Moduln teilerfremd sind. Beispiel: Chinesischer Restsatz teilerfremde Moduln im Video zur Stelle im Video springen (03:19) Gesucht sei eine ganze Zahl mit der Eigenschaft: Zum Finden einer Lösung wird nun die Argumentationskette des Beweises abgearbeitet. Zunächst wird das Produkt der teilerfremden Moduln gebildet: Somit lauten die ∶ Mit dem erweiterten euklidischen Algorithmus lassen sich ganze Zahlen und mit finden: Es gilt also für: Weiterhin gilt: Eine Lösung der simultanen Kongruenz lautet demnach Aufgrund der Tatsache sind also alle Lösungen kongruent zu 47 modulo 60.
Das Produkt M M stimmt hier wegen der Teilerfremdheit mit dem kgV überein. Finden einer Lösung Eine Lösung x x kann man wie folgt ermitteln. Für jedes i i sind die Zahlen m i m_i und M i: = M / m i M_i:= M / m_i teilerfremd, also kann man z. Chinesischer restsatz rechner. B. mit dem erweiterten euklidischen Algorithmus zwei Zahlen r i r_i und s i s_i finden, so dass r i ⋅ m i + s i ⋅ M i = 1 r_i \cdot m_i + s_i \cdot M_i = 1. Setzen wir e i: = s i ⋅ M i e_i:= s_i \cdot M_i, dann gilt e i ≡ 1 m o d m i e_i \equiv 1 \mod m_i e i ≡ 0 m o d m j, j ≠ i e_i \equiv 0 \mod m_j, \ j \neq i. Die Zahl x: = ∑ i = 1 n a i e i x:= \sum\limits_{i=1}^n a_i e_i ist dann eine Lösung der simultanen Kongruenz. Beispiel Gesucht sei eine ganze Zahl x x mit der Eigenschaft x ≡ 2 ( m o d 3) x ≡ 3 ( m o d 4) x ≡ 2 ( m o d 5) \array{ {x \equiv 2 {\pmod 3}} {x \equiv 3 {\pmod 4}} {x \equiv 2 {\pmod 5}}} Hier ist M = 3 ⋅ 4 ⋅ 5 = 60, M 1 = M / 3 = 20, M 2 = M / 4 = 15, M 3 = M / 5 = 12 M = 3 \cdot 4 \cdot 5 = 60, \ M_1 = M/3 = 20, \ M_2 = M/4 = 15, \ M_3 = M/5 = 12.
Wenn man die darzustellende Zahl normiert, also dafür sorgt, dass die Ziffer vor dem Komma eine eins ist, muss man die Vorkommastelle auch nicht mehr angeben. Nun werden Zahlen vom Rechner aber nicht im Dezimal- sondern im Binärsystem dargestellt. Deswegen müssen wir noch alles in dieses System umwandeln. Chinesischer Restsatz - Unionpedia. Um den Exponenten unabhängig von seiner Größe in der gegebenen Bitzahl angeben zu können, müssen wir ihn in die sogenannte Exzess-q-Schreibweise umwandeln. Dementsprechend wäre zum Beispiel "null Komma sieben fünf" gleich "eins Komma eins mal zwei hoch minus eins". Das könnte man wiederum schreiben als: Normierung Dabei setzen wir ganz einfach um, was wir gerade gelernt haben: Wir setzen das Vorzeichenbit auf null, da unsere Zahl positiv ist, schreiben unseren Exponenten in die richtige Schreibweise um und geben unsere Nachkommastellen in Binärform an. Wichtig dabei ist aber, dass wir uns an k halten müssen. Das heißt, wir füllen alle nicht benötigten Stellen mit Nullen auf. Gleitkommazahl berechnen Nun wollen wir uns die Gleitkommazahl noch an einem kurzen Beispiel anschauen.
(Wie versprochen kleiner als 5 * 12 * 77. ) Ich hoffe, du machst dir die Mühe, dies zu verstehen. Rudolf Verffentlicht am Dienstag, den 29. Mai, 2001 - 12:52: Die Berechnung der Zahl geht auch noch einfacher! Du fragst zunächst, welche Zahl T5 erfüllt die Gleichungen: T5 mod 5 = 1 T5 mod 12 = 0 T5 mod 77 = 0 Wegen 12*77 mod 5 = 4 muß 4*x mod 5 = 1 sein, also x = 4 und T5 = 4*12*77 Ebenso möge gelten: T12 mod 5 = 0 T12 mod 12 = 1 T12 mod 77 = 0 Wegen 5*77 mod 12 = 1 muß T12=5*77 sein. Chinesischer Restsatz – Wikipedia. Und letztlich: T77 mod 5 = 0 T77 mod 12 = 0 T77 mod 77 =1 Wegen 5*12 mod 77 = 60 muß 60*y mod 77 = 1 sein. Das gibt y = 9 und T77 = 9*5*12 Die gesuchte Zahl ist dann: z=((zmod5)*T5+(zmod12)*T12+(zmod77)*T77)mod5*12*77 Also für unser Beispiel: z=3*4*12*77+4*5*77+20*9*5*12 mod 5*12*77 = 328 Du mußt also nur einmal für jeden Faktor des Modulus eine Zahl berechnen und kannst damit alle Zahlen aus den gegebenen Resten ermitteln.
Gleichsetzen: 5a + 3 = 12b + 4 => 5a - 12b = 1 (1) Weißt du, wie man Gleichung (1) löst? Stichwort Euklidischer Algorithmus! Beachte: ggT(5, 12) = 1. Falls nein, frag noch mal. Ich sag' dir die Lösung von (1), ohne vorzurechen, wie ich drauf gekommen bin: ist a = 5, b = 2. Die allgemeine Lösung von (1) lautet: a = 5 + 12c, b = 2 + 5c (c beliebig) Mach die Probe! Also ergibt sich für x: x = 5a + 3 = 25 + 60c + 3 = 60c + 28 bzw. x = 12b + 4 = 24 + 60c + 4 = 60c + 28 Jetzt soll auch noch x = 20 mod 77 gelten. Also x = 77d + 20 Wieder gleichsetzen: 77d + 20 = 60c + 28 => 77d - 60c = 8 (2) Um (2) zu lösen, löse zunächst 77e - 60f = ggT(77, 60) = 1 Hier wieder die Lösung ohne Rechnung: e = 53, f = 68. Für die Lösung von (2) wird das einfach mit 8 multipliziert: c = 8f = 544, d = 8e = 424. Die allgemeine Lösung von (2) lautet c = 544 + 77g, d = 424 + 60g. Also x = 60c + 28 = 32640 + 4620g + 28 = 32668 + 4620g bzw. x = 77d + 20 = 32648 + 4620g + 20 = 32668 + 4620g Die kleinste Lösung erhältst du, wenn du g = -7 setzt: x = 328.