Autor |
Beitrag |
me
| Veröffentlicht am Freitag, den 17. November, 2000 - 17:13: |
|
Hi, kann mir jemand das mit dem chinesischen Restsatz nochmal erklären? Bei unserem Prof habe ich den leider gar nicht verstanden. Schritt für Schritt und ausführlich für Doofe wär nett. |
Zaph (Zaph)
| Veröffentlicht am Samstag, den 18. November, 2000 - 17:21: |
|
Am besten ein Beispiel. Gesucht ist eine Zahl x, die durch 5 geteilt den Rest 3, durch 12 geteilt den Rest 4 und durch 77 geteilt den Rest 20 lässt: x = 3 mod 5 x = 4 mod 12 x = 20 mod 77 Aus dem chinesische Restsatz folgt, dass es solch eine Zahl gibt, weil 5, 12 und 77 paarweise teilerfremd sind. Die kleinste positive Zahl mit den Eigenschaften ist kleiner als 5 * 12 * 77. |
me
| Veröffentlicht am Mittwoch, den 22. November, 2000 - 14:41: |
|
Und wie kann man die Schritt für Schritt berechnen? |
Zaph (Zaph)
| Veröffentlicht am Mittwoch, den 22. November, 2000 - 21:21: |
|
Du fängst an, ein x zu bestimmen mit x = 3 mod 5 x = 4 mod 12 Es soll also gelten x = 5a + 3 x = 12b + 4 für gewisse a, b. 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. (Wie versprochen kleiner als 5 * 12 * 77.) Ich hoffe, du machst dir die Mühe, dies zu verstehen. |
Rudolf
| Veröffentlicht 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. 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. |
|