| Autor |
Beitrag |
    
Melanie (Miss_Sinus)
| | Veröffentlicht am Dienstag, den 23. Oktober, 2001 - 12:47: | 
|
Kann mir jemand verständlich erklären, was genau der Chinesische Restsatz ist und wie ich mir die Rechnung anhand eines Beispiels vorstellen muss?
Danke |
H.R.Moser,megamath.
| | Veröffentlicht am Mittwoch, den 24. Oktober, 2001 - 08:04: |
|
Hi Melanie,
Zunächst ein paar Begriffe:
Der chinesische Restsatz ist nichts anderes als der so genannte
Hauptsatz der Simultankongruenzen.
Eine Simultankongruenz liegt vor, wenn eine Zahl x gesucht wird ,
die gleichzeitig (simultan) mehreren Konguenzbedingungen modulo verschiedener Zahlen genügt, etwa so:
x == r1 modulo a1
x == r2 modulo a2
.............................
x == rn modulo an
Dabei bedeutet " == " das Kongruenzzeichen ,
a1,a2..,r1,r2,..sind gegebene Zahlen
Die Zahl x wird gesucht.
Der erwähnte Hauptsatz ( Chinesischer Restsatz ) lautet:
Jede Simultankongruenz mit paarweise teilerfremden Moduln
a1,a2...,an ist lösbar und die Lösung x besteht genau in einer
Restklasse modulo dem Produkt A = a1*a2 *...*an dieser Moduln.
Um das Verständnis zu fördern, arbeiten wir zunächst nur mit zwei
Moduln a1 = a und a2 = b ; als Zahlenbeispiel wählen wir
a = 5 , b = 7. ( a und b sind teilerfremd, ihr Produkt ist A = 35 )
Die Aufgabe laute etwa
Gesucht wird x derart , dass die Kongruenzen
x == 2 modulo 5
x == 4 modulo 7
simultan gelten.;
als Lösung findet man x = 32
( oder x = 32 + 35 = 67 , oder x = 67 + 35 = 102 usw.)
Ueberzeuge Dich von der Richtigkeit durch eine einfache Kopfrechnung !
Wir erstellen eine aufschlussreiche Tabelle für a = 5 , b = 7
In der ersten Zeile stehen die Repräsentanten 0,1,2,3,4,5,6
der Restklassen modulo 7
In der ersten Kolonne die Repräsentanten der Restklassen
modulo 5,nämlich 0,1,2,3,4
...........0........1........2...........3.........4...... ....5.........6
0.........0.......15.......30........10......25......... ..5 ......20
1.......21.........1.......16........31......11..........26.........6
2.........7........22.........2........17.......32..........12.........27
3........28.........8.......23..........3.......18...........33........13
4........14........29........9........24.........4...........19........34
Interpretiere die Tabelle:
Die oben erwähnte Lösung x = 32 steht in der Zeile '2'
und der Kolonne '4'.
Studiere den Aufbau der Tabelle ,welche für a = 5,b=7
total 35 simultane Gleichungen liefert.
Dazu noch ein Beispiel
Die simultanen Kongruenzen
x == 4 modulo 5
x == 1 modulo 7 hat die Lösung
x = 29 , wenn wir uns auf die Tabelle und unser Rechenkünste
verlassen können.
Fortsetzung folgt
Mit freundlichen Grüßen
H.R.Moser,megamath. |
H.R.Moser,megamath.
| | Veröffentlicht am Mittwoch, den 24. Oktober, 2001 - 09:48: |
|
Hi Melanie,
Zur Struktur der Tabelle, welche für das
Zahlenbeispiel
a = 5, b=7 dienlich ist
(siehe meine letzte Arbeit zu diesem Thema)
a) Betrachte die Hauptdiagonale des Schemas ,
welche von links oben nach rechts unten geht ;
sie enthält die Zahlen 0 , 1 , 2, 3, 4.
allgemein: 0,1,2,3,.....,a-1
b) In den dazu parallelen Schrägreihen stehen
aufeinander folgende Zahlen: 21,22,23,24 u.s.w.
c) ganz rechts unten steht a * b - 1 = 34
d) In den Zeilen stehen arithmetische Folgen
modulo a* b = 35 mit der Differenz d = 15
als Lösung der simultanen Kongruenzen
d == 0 modulo 5 und d == 1 modulo 7
e) In den Kolonnen stehen analog arithmetische
Folgen modulo 35 mit der Differenz u = 21
als Lösung der simultanen Kongruenzen
u == 1 modulo 5 und u == 0 modulo 7.
Wie löst man algebraisch ein solches Simultansystem ?
Beispiel:
x == 2 modulo 5
x == 4 modulo 7
Wir kennen bereits aus der Tabelle den
Repräsentant x = 32 (modulo 35) als Lösung
Die erste Gleichung wird mit 7 die zweite mit 5 multipliziert
Wir erhalten:
7*x == 14 modulo 35
5* x == 20 modulo 35
Nun addieren wir die beiden Zeilen:
12 * x == 34 modulo 35
Der kleinste positive x-Wert ,welcher diese Kongruenz
befriedigt,
ist x = 32, jedenfalls ist
12 * 32 -34 = 350 durch 35 teilbar
Mit freundlichen Grüßen
H.R.Moser,megamath. |
H.R.Moser,megamath.
| | Veröffentlicht am Mittwoch, den 24. Oktober, 2001 - 10:24: |
|
Hi Melanie,
Zur Geschichte des Chinesischen Restsatzes
( Zitate aus dem ausgezeichneten Lexikon
der Mathematik, Spektrum Verlag )
In einem chinesische Text des 1.Jahrhunderts n.Chr.
findet man die Aufgabe, eine Zahl zu finden,
die bei der Division durch 3,5,7 nacheinander die
Reste 2,3,2 lässt.
Im Text werden zunächst die Hilfszahlen 70, 21,15
als geeignete Vielfache von 5*7, 3*7, 3*5 bestimmt ,
um auf die Lösung
2* 70 + 3*21 +2*15 = 233 zu kommen.(!)
Subtrahiert man davon ein geeignetes Vielfaches von
3*5*7 =105 , so kommt mit 23 die kleinste
positive Lösung .
Das gleiche Problem samt Lösung findet man auch bei
Nicomachus in einer Abhandlung ca. 100 n.Chr.
Die Bezeichnung "Chinesischer Restsatz" rührt davon
her, dass die Regel 1852 von A.Wylie in einem
Artikel
"Jottings on the science of the Chinese arithmetie"
in Europa bekannt gemacht wurde.
Zitat Ende.
Mit freundlichen Grüßen
H.R.Moser,megamath. |
H.R.Moser,megamath.
| | Veröffentlicht am Donnerstag, den 25. Oktober, 2001 - 08:18: |
|
P.P.
Zur Abrundung des Themas möchte ich noch eine
Ergänzung anbringen.
In einer Geschichte der Mathematik aus der Sammlung
Göschen (Band 226) ist nachzulesen :
< Im Wu-ts'ao suan-king (verfasst von Suntzi,1.Jahrh.n.Chr.)
wird das von nun an bei Indern, Arabern und Abendländern
immer wiederkehrende Beispiel
x = 3 * t1 + 2 = 5 * t2 + 3 = 7 * t3 + 2
[ = qi * ti + ri ]
vorgeführt.
Die originelle chinesische Methode vermittels
der " grossen Erweiterung " stützt sich auf die Lösung
der Hilfsgleichungen
q2*q3*u1 =q1*v1 + 1 usw.
(in möglichst kleinen Zahlen durch Erraten )
Dann ist der Rest bei Division von
Sum [ q2*q3*r1*u1 ] durch q1*q2*q3 eine Lösung >
Es sollen nun zwei Beispiele mit dreigliedrigen Kongruenzen
mit einer modifizierten chinesischen Methode
durchgerechnet werden.
1.Beispiel
Kongruenzen:
x == 2 (modulo 7), x== 4 (modulo 8) , x ==1 (modulo 9)
Gesucht wird x als Repräsentant der Restklassen modulo
A= 7*8*9= 504
Beachte : die Moduln 7 , 8 , 9 sind paarweise teilerfremd..
Wir bilden q1 = 8*9 = 72, q2 = 9*7 = 63 , q3 = 7*8 = 56.
Daraus
q1*y1 = 72*y1 == 2*y1 == 1 (modulo 7),
mithin y1 == 4 (modulo 7)
q2*y2 = 63*y2 == - y2 ==1 (modulo 8) ,
mithin y2 == - 1 (modulo 8)
q3*y3 = 56*y3 ==2*y3 == 1 (modulo 9)
mithin y3 == - 4 (modulo 9)
Schluss: mit ei = qi*yi (modulo(A) erhalten wir
e1 = 72* 4 (modulo504 ) = 288 (modulo 504)
es = 63* (-1) (modulo(504) = - 63 (modulo 504)
e3 = 56* (-4) (modulo(504) = - 224 (modulo 504)
Schliesslich x:
x = 2 * e1 + 4* e2 + 1* e3 = 576- 252 - 224 (modulo (504)
x = 100 (modulo 504)
°°°°°°°°°°°°°°°°°°°°°°
2.Beispiel
Kongruenzen:
x == 5 (modulo 7), x== 1 (modulo 8) , x ==3 (modulo 9)
Lösung
Deckungsgleiche Rechnung am Anfang
Schluss:
x = 5 * e1 + 1 * e2 + 3 * e3 =
x = 5 * 288 - 63 - 3*224 == 705 (modulo504),also:
x = 201 (modulo504)
°°°°°°°°°°°°°°°°°°°°°
Mit freundlichen Grüßen an alle Interessierten
H.R.Moser,megamath. |
|
