Simultane Kongruenzen

[noRkia]

mein problem ist folgendes:

ist zb. gegeben: (= soll das kongruenzzeichen sein)

x = a mod p

x = b mod q

x = c mod r

dann wende ich den chinesischen restsatz an.
nur musste ich eben beim durchgehen von beispielaufgaben von hier und dort
feststellen das es auch solche kongruenzen gibt bei denen vor dem x in jeder zeile verschiedene faktoren stehen.zb:

9x = 6 mod 11

12x = 5 mod 7

2x = 4 mod 6

dann funktioniert die bisherige vorgehensweise nicht mehr weil ich rechne ja dann die lösung für den fall aus das überall eine 1 davor steht.
diese lösung eingesetzt ist aber natürlich falsch.

auf was muss man hier achten um das zu lösen?

[TheBiber]

Bah, diskrete Mathematik. Ein Glück bin ich dieses Fach für den Rest meines Lebens los. :D Die Klausur war erst vorgestern, hab das Zeugs also noch ziemlich präsent.

Wenn man den Ausdruck a = b mod n betrachtet, dann darf man a und b "kürzen", wenn a und b teilerfremd zu n sind:

ac = bc mod n <=> a = b mod n genau dann wenn ggT(c,n) = 1.

In deinem Problem wäre eine Methode, indem du die Vorfaktoren aller Gleichungen auf deren kgV bringst. Dann kannst du den chinesischen Restsatz anwenden und anschliessend mit obigem Satz überprüfen, ob ganzzahlige Lösungen für die x möglich sind.

[noRkia]

wenn ich das mache steht in der 3tten zeile:

216 = 4*108 mod 6

4* 108 ist gleich 436 = 0 mod 6

damit das ganze ding aber nicht lösbar denn der ggt( 11*7;6) ist 1 und damit ungleich 0?

[TheBiber]

Ich sehe gerade das Problem: kgV(9,12,2) = 36. Aber ggT(36,6) = 6, somit darfst du die dritte Gleichung erst gar nicht erweitern.

Eine Alternative Methode wäre, du löst jede Gleichung einzeln und überprüfst, ob die Lösungsmenge aller drei Gleichungen gemeinsame Elemente enthalten. Zum Beispiel lässt sich 9x = 6 mod 11 umschreiben als 9x+6t = 11. Mit dem erweiterten euklidischen Algorithmus findest du eine Lösung für 9x+6t=ggt(9,6)=3, diese Lösung musst du dann so umrechnen, dass die erste Gleichung erfüllt ist, wenn dies überhaupt noch möglich sein sollte. Anschliessend bestimmst du noch die homogene Lösung, d.h. die Lösung von 9x+6t = 0 und superponierst sie mit deiner ersten gefundenen Lösung. Dieses Verfahren wendest du auf alle drei Gleichungen an und bildest anschliessend die Schnittmenge der drei Lösungsmengen, diese enthalten, sofern sie nicht leer sind, unendlich Lösungen.

Ist unglaublich umständlich, aber eine einfachere Methode ist mir nicht bekannt.

[noRkia]

in den beiden demoklausuren die mir seit gestern vorliegen komm es dran argh ;/

edit:

HA! mit den jeweiligen einheiten der moduln multiplizieren!

:D