Problem bei bestimmter Aufgabe
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Chin. Restesatz
Hallo,
ich denk ich hab grad eine Blockade oder hab die Modulare Arithmetik doch noch nicht verstanden, aber beim chinesischen Restesatz hab ich bei einer Aufgabe ein Problem:
Gelöst werden soll x ≡ 2 mod 9 und x ≡ 4 mod 10.
Ich muss ja einmal eggT(10, 9) und einmal eggT(9, 10) machen, aber das geht ja wegen a > b nicht… Wie kommen die jetzt in ihrer Lösung auf den Bezout-Koeffizienten e1 = 1(logisch) und e2 = 9(???)?
Wie gesagt, bei anderen chin. RS-Aufgaben hab ich (bis jetzt! g) keine Probleme, nur da hörts auf…
hoi
also du musst nur den ggt(10,9) rechnen wie du richtig erkannt hast, bringt der ggt (9,10) nix bzw. nur das gleiche ergebniss…
am schluss steht da : 1 * 10 - 1 * 9 = 1
so dann machst du einfach 1 * 10 * 2 (das ist für die 9 )
und -1 * 9 * 4 (das ist für die 10)
bezout koeffizienten sind 1 und -1
also : 1 * 10 * 2 - 1 * 9 * 4 = -16 (mod 10 * 9)
also -16 = 74 (im ring 90)
74 ≡ 2 mod 9 und 74 ≡ 4 mod 10
hoffe das hilft dir…
Jo danke hat mir sehr geholfen 
War nämlich von der seltsamen Lösung so irritiert, dass ich dann nicht mehr weiter wusste…aber klingt logisch, einfach die Bezout-Koeffizienten von ggT(10,9) für beides zu nehmen d’oh’
Wenn ich net noch so viel anderes für TI zu tun hätte, würde mich aber trotzdem interessieren, wie die auf 2110+499 kommen. Vielleicht ein Fehler im Aufgaben-Generator? 
die rechnen die Faktoren schon in die Zahlen in den kleinen Ringen um bevor sie damit rechnen, also -1 mod 10 = 9 und 1 mod 9 = 1…glaub ich…:o)
gleiches thema, andre frage 
bin bei der uebungsaufgabe 35) 1.
das mit dem eggT ist mir klar und ich krieg auch die Bezout-Koeffizienten raus, aber dann wenn ich die Gleichung aufstelle um das Ergebnis zum Produkt zu kriegen, weiss ich nicht so genau wies geht.
Die Frage ist, welche Zahl vorm mod man nimmt.
Also ich habe jetzt:
eggT(110,9): -4110 + 499 = 1
eggT(90,11): -590 + 4111 = 1
eggT(99,10): -199 + 1010 = 1
Dann muss ich doch die Gleichung aufstellen, um mein Produkt
aus 23*41 rauszukriegen und evtl. mod 990 nehmen,
aber woher weiss ich welche Zahl als erster kommt
-4110x + (-5)90y + (-1)99z = v mod990
jetzt ist nur die frage was x,y,z ist
danke schon mal im voraus
Z9
23 mod 9 = 5
41 mod 9 = 5
5*5 mod 9 = 7
Z10
23 mod 10 = 3
41 mod 10 = 1
3*1 mod 10 = 3
Z11
23 mod 11 = 1
41 mod 11 = 8
1*8 mod 11 = 8
einsetzen
x = 7 y = 3 z = 8
-41107 + (-5)903 + (-1)998 = v mod990
-110 - 135 - 792 mod 990 = -47 mod 990 = 943 mod 990
ok danke perfekt jetzt geht alles