Simultanen Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:05 Fr 21.03.2014 | | Autor: | DieNase |
| Aufgabe | Man bestimme die Lösungen der folgenden simultanen Kongruenzen:
a)
[mm] x\equiv3 [/mm] mod 4
[mm] x\equiv2 [/mm] mod 5
[mm] x\equiv1 [/mm] mod 7
[mm] x\equiv0 [/mm] mod 9
b)
[mm] x\equiv19 [/mm] mod 21
[mm] x\equiv25 [/mm] mod 39
[mm] x\equiv12 [/mm] mod 77
[mm] x\equiv12 [/mm] mod 143 |
Wenn ich alles richtig verstanden habe ist M:kgV(m1,m2,m3,m4)
M1 = M / m1 Und dann wird alles mit dem Chinesischen Restsatz gelöst. In Beispiel 1 ist das kgV(4,5,7,9) = 4*5*7*9
da ggT(4,5,7,9) = 1.
Das Beispiel b gibt mir hier aber andere aufgaben die ich net verstehe 
muss ich hier [mm] x\equiv12 [/mm] mod 77 und [mm] x\equiv12 [/mm] 143 irgendwie zusammen fassen aller [mm] x\equiv [/mm] mod kgv(77,143)
und was ist wenn ich [mm] x\equiv2 [/mm] mod 5 und [mm] x\equiv2 [/mm] mod 10 habe???
Gibt es hier eine standartlösung oder nach welchen gesichtspunkten muss ich das hier lösen? Ich versteh nicht ganz wann darf ich einfach stumpf holzhacker methode anwenden und durchrechnen und WANN heißt es ACHTUNG zuerst denken.
Meine bisherige Faustregel:
[mm] x\equiv [/mm] y mod m
gibt es kein gleiches y in den gleichungen und sind alle ms teilerfremd dann nimm die Axt und hau drauf.
Doch was ist wenn, es 2 gleiche y gibt oder mehrerer?
was ist wenn die mod m nicht teilerfremd sind was ist dann zutun?
Ich möchte keine Lösung der Beispiel ich suche nach wissen um sie selbstständig zu lösen
mfg
Christoph
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:43 Fr 21.03.2014 | | Autor: | Teufel |
Hi!
Wenn die Modulozahlen nicht teilerfremd sind, hast du immer die Möglichkeit die Zahlen zu faktorisieren und damit erst einmal mehr Gleichungen zu erschaffen.
z.B.
[mm] $x\equiv [/mm] 2 [mm] \mod [/mm] 5$
und
[mm] $x\equiv [/mm] 2 [mm] \mod [/mm] 10$
wird zu
[mm] $x\equiv [/mm] 2 [mm] \mod [/mm] 5$
und
[mm] $x\equiv [/mm] 2 [mm] \mod [/mm] 2$
[mm] $x\equiv [/mm] 2 [mm] \mod [/mm] 5$
nachdem die Gleichung [mm] $\mod [/mm] 10$ aufgesplittet wurde. So kannst du dir immer teilerfremde Zahlen erschaffen, oder du siehst direkt, dass es keine Lösung gibt, wenn sich zwei Gleichungen wiedersprechen.
Ob dort deine y gleich sind, ist egal.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:43 Sa 22.03.2014 | | Autor: | DieNase |
Also bedeutet das für mich folgendes:
Ich erschaffe soviel gleichungen wie nötig. Als Beispiel:
x [mm] \equiv [/mm] 5 mod 12
x [mm] \equiv [/mm] 8 mod 24
dann lös ich auf:
x [mm] \equiv [/mm] 5 mod 12
x [mm] \equiv [/mm] 8 mod 12
x [mm] \equiv [/mm] 8 mod 2
dann hätte ich immernoch das problem. Ich würde also weiter auflösen
x [mm] \equiv [/mm] 8 mod 3
x [mm] \equiv [/mm] 8 mod 4
x [mm] \equiv [/mm] 8 mod 2
x [mm] \equiv [/mm] 5 mod 12
das wäre doch jetzt folgendes:
x [mm] \equiv [/mm] 8 mod 3
x [mm] \equiv [/mm] 0 mod 4
x [mm] \equiv [/mm] 0 mod 2
x [mm] \equiv [/mm] 5 mod 12
wäre das dann richtig aufgelöst?
Wäre dann nicht gleich:
x [mm] \equiv [/mm] 8 mod 8
und somit
x [mm] \equiv [/mm] 0 mod 8.
Welche gleichungen verwendet ich jetzt?
Zum anderen wie beurteile ich z.b. folgendes:
x [mm] \equiv [/mm] 5 mod x
x [mm] \equiv [/mm] 8 mod x
sagen wir ich hätte aufgeteilt und ich hätte 2 mal mod x erhalten und aber vorne stehen 2 unterschiedliche Zahlen so müsste ich hier doch zum schluss kommen nicht lösbar oder? (Sofern 8 mod x nicht die gleich restklasse wie 5 mod x ist).
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:53 Sa 22.03.2014 | | Autor: | Teufel |
Hi!
Also an der Stelle
$x [mm] \equiv [/mm] 5 [mm] \mod [/mm] 12$
$x [mm] \equiv [/mm] 8 [mm] \mod [/mm] 12 $
kannst du schon aufhören, weil sich diese 2 Gleichungen widersprechen! Würde es nämlich so ein $x$ geben, das beide erfüllt, so kannst du ja mal beide Gleichungen voneinander abziehen und dann sollte etwas Falsches herauskommen.
Wenn sich also 2 Gleichungen widersprechen, kannst du aufhören!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:25 Sa 22.03.2014 | | Autor: | DieNase |
Ich danke dir mal für deine Geduld mit mir
Ich glabue ich habe gerade ein Durchbruch in sachen simultanen kongruenzen.
Aber zu meinem Durchbruch der hoffentlich richtig ist:
ich habe das bsp: b aus meiner ersten angabe vor mir die lautet
x [mm] \equiv [/mm] 19 mod 21
x [mm] \equiv [/mm] 25 mod 39
x [mm] \equiv [/mm] 12 mod 77
x [mm] \equiv [/mm] 12 mod 143
Primfaktorzerlegung:
21 = 3 * 7
39 = 3 * 13
77 = 11 * 7
143 = 11 * 13
D.h. ich erhalte folgende 8 kongruenzen:
x [mm] \equiv [/mm] 19 mod 3
x [mm] \equiv [/mm] 19 mod 7
x [mm] \equiv [/mm] 25 mod 3
x [mm] \equiv [/mm] 25 mod 13
x [mm] \equiv [/mm] 12 mod 11
x [mm] \equiv [/mm] 12 mod 7
x [mm] \equiv [/mm] 12 mod 11
x [mm] \equiv [/mm] 12 mod 13
Ich habe jetzt folgendes gemacht: Es gibt keine Kongruenz die sich widerspricht und ich kann das ganze auf 4 kongruenzen der form:
x [mm] \equiv [/mm] 1 mod 11
x [mm] \equiv [/mm] 12 mod 13
x [mm] \equiv [/mm] 5 mod 7
x [mm] \equiv [/mm] 1 mod 3
zurückführen. Ich habe geschaffen simultane kongruenzen die Teilerfremd sind da alle mod m zahlen primzahlen sind. Somit kann ich ganz normal mit dem Chinesischen Restsatz das Beispiel lösen.
Meine durchbruch möchte ich so formulieren.
1. Wenn alle mod m teilerfremd sind -> Axt nehmen und sich durchschlagen
2. Wenn sie nicht teilerfremd sind -> Aufteilen in Primfaktoren der mod m (oder bis sie teilerfremd sind)
3. Die nun entstandenen Kongruenzen auf widersprüche prüfen
4. Im falle keines widerspruch -> AXT und durch den wald durchschlagen mit dem Chinesischen Restsatz.
Kann ich mir das als grobe vorgehensweise merken?
mfg
Christoph
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:01 Sa 22.03.2014 | | Autor: | Teufel |
Heya!
Ganz genau! Das klappt immer, denn spätestens bei der Primfaktorzerlegung sind ja alle Modulzahlen teilerfremd. oft kannst du natürlich schon vorher aufhören, aber klappen tut es immer, wenn du es ganz bis zum Ende machst, so wie in deinem Beispiel.
|
|
|
|
