Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Chinesischer Restsatz

ZahlReich - Mathematik Hausaufgabenhilfe » ---- Archiv: Universitäts-Niveau » Zahlentheorie » Chinesischer Restsatz « Zurück Vor »

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

me
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 17. November, 2000 - 17:13:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Samstag, den 18. November, 2000 - 17:21:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

me
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Mittwoch, den 22. November, 2000 - 14:41:   Beitrag drucken

Und wie kann man die Schritt für Schritt berechnen?
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Mittwoch, den 22. November, 2000 - 21:21:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Rudolf
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 29. Mai, 2001 - 12:52:   Beitrag drucken

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.

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page