Kongruenzgleichungen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:07 Di 12.07.2005 | | Autor: | Winfoman |
Ich habe Probleme beim Lösen von Kongruenzgleichungen folgender Form:
[mm] 192\*x [/mm] + 116 [mm] \equiv [/mm] 77 (mod 105)
wobei x [mm] \in \IZ_{105}
[/mm]
Ich habe hier einen Lösungsweg für Gleichungen in der Form [mm] a\*x \equiv [/mm] b (mod m), d.h. meine Lösungsversuche scheitern bereits an der "+116". Kann mir jemand da bitte mal eine kleine Starthilfe geben und auch beschreiben, wie es weitergeht? Ich habe den Lösungsweg nämlich noch nicht ganz verstanden. Ich weiß nur die Lösungen für ggT (a,m) = 1 und ggT (a,m) > 1 und teilt b nicht.
Gruß,
Winfoman
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Winfoman,
Deine Gleichung lässt sich folgendermaßen lösen:
192*x + 116 [mm] \equiv [/mm] 77 mod 105
Zunächst reduzieren wir alle Koeffizienten modulo 105:
87*x + 11 [mm] \equiv [/mm] 77 mod 105
Erst das Leichte:
87*x [mm] \equiv [/mm] 66 mod 105
Es gilt ggT(87,105)=3. Das ist schlecht, aber glücklicherweise ist 3 auch ein Teiler von 66. D.h.: Wir können die 3 aus der Gleichung "herausheben", und erhalten:
29*x [mm] \equiv [/mm] 22 mod 35
Nun gilt ggT(29,35)=1. Wir können also durch 29 dividieren, und erhalten:
x [mm] \equiv [/mm] 8 mod 35.
Nun müssen wir diese Lösung wieder von [mm] \IZ_{35} [/mm] nach [mm] \IZ_{105} [/mm] hochheben, und erhalten die Lösungen
x [mm] \equiv [/mm] 8, 43, 78 mod 105.
Zum Schluss noch die Probe. Es gilt:
192*8 + 116 [mm] \equiv [/mm] 77 mod 105
192*43 + 116 [mm] \equiv [/mm] 77 mod 105
192*78 + 116 [mm] \equiv [/mm] 77 mod 105
Somit sind die ermittleten Zahlen tatsächlich Lösungen der ursrünglichen Gleichung, und das Problem ist gelöst.
Liebe Grüße,
Holy Diver
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:56 Di 12.07.2005 | | Autor: | Winfoman |
Hallo Holy Diver!
Zunächst mal danke für deine ausführliche und sehr hilfreiche Antwort.
Aber zwei Fragen habe ich noch:
1. Wie kommst du bei der Division durch 29 auf die 8?
2. Wie funktioniert das Anheben der Lösung? Da ist mir nur klar, dass es wegen ggT=3 3 Lösungen geben muss.
Gruß,
Winfoman
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:20 Mi 13.07.2005 | | Autor: | Stefan |
Hallo!
> 1. Wie kommst du bei der Division durch 29 auf die 8?
Zum Beispiel kannst du mit dem erweiterten Euklidischen Algorithmus nachrechnen, dass $-6$ ein Inverses von $29$ in [mm] $\IZ_{35}$ [/mm] ist. Man multipliziert also die Gleichung mit $-6$.
Es gilt aber:
$22 [mm] \cdot [/mm] (-6) = -132 = (-4) [mm] \cdot [/mm] 35 +8 [mm] \equiv [/mm] 8 [mm] \pmod{35}$.
[/mm]
> 2. Wie funktioniert das Anheben der Lösung? Da ist mir nur
> klar, dass es wegen ggT=3 3 Lösungen geben muss.
Du musst alle Repräsentanten im Bereich [mm] $0,1,2\ldots,104$ [/mm] finden, die kongruent zu $8$ modulo $35$ sind. Das machst du, indem du zu $8$ so lange $35$ addierst, bist du die $104$ überschritten hast (höre vor dem Überschreiten auf).
Viele Grüße
Stefan
|
|
|
|
