simultane kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | berechnen Sie:
12 x = 7 mod 25
x= 2 mod 21 |
hmm, auch wenn die letzte Frage hier das gleiche Thema behandelt hat, muss ich dennoch neu fragen.
Da die Koeffizienten von x nicht gleich sind, muss ich zunächst umstellen, also:
x = 2 mod 21 <--> 12x = 3 mod 21
Da ggt(21,25)=1 folgt nun:
1 = -5 * 25 + 6 * 21
--> 7*(-125) + 3 * 126 = -497
So, gäbe es jetzt nicht den Koeffizienten "12", dann wäre -497 doch die Lösung, oder? - Leider (zumindest aus meiner Sicht) ist -497nicht durch 12 teilbar. Wie kann ich denn jetzt das tatsächliche x finden?
Hoffe, ihr könnt mir helfen...
Liebe Grüße
Sabine
|
|
| |
|
Hallo Sabine,
Du bestimmst also ein y, das [mm] \mod{21} [/mm] und [mm] \mod{25} [/mm] äquivalent zu 12x ist.
Leider erfüllt Deine Lösung aber die geforderten Kongruenzen nicht. Da hast Du Dich verrechnet.
Aber selbst wenn es stimmen würde:
Dass 472 nicht durch 12 teilbar ist, ist natürlich richtig. [mm] \mod{25} [/mm] lässt sich das ja noch lösen, indem mit dem multiplikativ Inversen zu 12 multipliziert, also der 23.
Um die aber zu finden, ist der Aufwand genauso hoch wie der, schon vor der Lösung der simultanen Kongruenz alle Äquivalenzen auf [mm] x\equiv\cdots [/mm] zu bringen.
Das zweite Problem an der Sache ist, dass wegen [mm] ggT(12,21)=3\not=1 [/mm] die 12 kein multiplikatives Inverses [mm] \mod{21} [/mm] besitzt.
So, in der Problemanzeige ist nun auch schon der Tipp verborgen, wie Du die erste Kongruenz auf die gesuchte Form [mm] x\equiv\cdots [/mm] bringst.
Also nochmal das Ganze...
Grüße
reverend
|
|
|
| |
|
also nochtmal das Ganze...:
12x = 7 mod 25
<--> (12*23)*x = 7*23 mod 25
<--> x = 11 mod 25
stimmt das soweit (sry, hatte eben ein paar Rechen-/Schreibfehler drin)
so, dann habe ich jetzt also:
x=11 mod 25
x=2 mod 21
1= (-5)*25 + 6*21
--> x=11*126+3*(-125) = 1136
so, jetzt stimmts 
vielen Dank für deine Hilfe
|
|
|
| |
|
Hallo nochmal,
schön, so stimmts.
Die Lösung ist trotzdem noch ein bisschen unübersichtlich.
Zum Schluss solltest Du noch folgende Äquivalenz notieren:
[mm] 1136\equiv 86\mod{(21*25)}
[/mm]
Die Lösung ist dann also [mm] 86\mod{525}, [/mm] unterscheidet sich aber nur in der Form von der von Dir errechneten. Trotzdem wird meist die "kleinste" Restklasse erwartet, die man dann angeben kann.
Grüße
reverend
|
|
|
|
