Kongruenzsysteme lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:49 Fr 17.06.2011 | | Autor: | Hanz |
Hallo, ich bräuchte mal Hilfe zum Thema lineare Kongruenzsysteme lösen. Nehmen wir folgendes:
Folgende Kongruenzen sollen modulo 82 bestimmt werden:
[mm] x_2 [/mm] = 1
[mm] 2*x_3 [/mm] + [mm] x_5 [/mm] = 7
[mm] x_7 [/mm] = 8
[mm] x_3 [/mm] + [mm] x_5 [/mm] = 17
[Anmerkung: Es sollen [mm] x_2, x_3, x_5 [/mm] und [mm] x_7 [/mm] berechnen lassen, nicht verwirren lassen, dass sie nicht [mm] x_1,..., x_4 [/mm] heißen =P ]
Meine erste Frage wäre: Wann bzw. wie weiss ich, dass ein Kongruenzsystem modulo n eindeutig lösbar ist?
Nun weiss ich, dass wenn ich ein System modulo 82 bestimmen soll, dies tun kann, indem ich 82=2*41 in Primfaktoren zerlegen und jeweils ein System modulo 2 und ein modulo 41 berechne. Mit dem chinesischen Restsatz erhalte ich dann das Ergebnis für das ganze System mod 82.
Nun ist mir nicht ganz klar, warum man dies in 82=2*41 teilt: tut man dies, weil [mm] Z_{82}^{\times} [/mm] kein Körper ist und somit keine Inversen besitzt, aber mod 2 und mod 41 dies schon erfüllen?
Was genau steckt beim chinesischen Restsatz dahinter, dass er aus den Teilsystemen aufs ganze System die Lösung ausgibt?
Wäre seeeehr dankbar für Hilfe!!!
P.S.: Ich weiss, dass mein System oben sehr einfach ist und durch etwas probieren auch so lösbar ist, muss das Problem aber auch auf komplexere Systeme übertragen und da fruchtet diese Methode nicht.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Hallo, ich bräuchte mal Hilfe zum Thema lineare
> Kongruenzsysteme lösen. Nehmen wir folgendes:
>
> Folgende Kongruenzen sollen modulo 82 bestimmt werden:
>
> [mm]x_2[/mm] = 1
> [mm]2*x_3[/mm] + [mm]x_5[/mm] = 7
> [mm]x_7[/mm] = 8
> [mm]x_3[/mm] + [mm]x_5[/mm] = 17
Für dieses System braucht man wirklich keine besonderen
Kenntnisse wie Restsatz etc.
Erstens sind die Gleichungen für [mm] x_2 [/mm] und für [mm] x_7 [/mm] nicht
miteinander und nicht mit dem Rest verknüpft und
stellen deshalb schon ihre eigenen Lösungen dar,
eben [mm] x_2=1 [/mm] und [mm] x_7=8 [/mm] (beides modulo 82).
Aus den anderen beiden Gleichungen erhält man
durch Differenzbildung sofort [mm] x_3=72 [/mm] und dann [mm] x_5=27 [/mm] .
Um die Techniken mit Einsatz der Theorie zu demonstrieren,
ist das Beispiel also ungeeignet, weil zu einfach !
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:04 Fr 17.06.2011 | | Autor: | Hanz |
Das hatte ich unter P.S. im obigen Post ja geschrieben. Habe das Beispiel nur geschrieben, damit man sich evtl. an einem 4-er System orientieren kann. Mir geht es auch eher um den theoretischen Teil, wann so ein System modulo n eindeutig lösbar ist und warum man kompliziertere Systeme auf die Primfaktoren reduziert.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:55 Fr 17.06.2011 | | Autor: | felixf |
Moin!
> Hallo, ich bräuchte mal Hilfe zum Thema lineare
> Kongruenzsysteme lösen. Nehmen wir folgendes:
>
> Folgende Kongruenzen sollen modulo 82 bestimmt werden:
>
> [mm]x_2[/mm] = 1
> [mm]2*x_3[/mm] + [mm]x_5[/mm] = 7
> [mm]x_7[/mm] = 8
> [mm]x_3[/mm] + [mm]x_5[/mm] = 17
>
> [Anmerkung: Es sollen [mm]x_2, x_3, x_5[/mm] und [mm]x_7[/mm] berechnen
> lassen, nicht verwirren lassen, dass sie nicht [mm]x_1,..., x_4[/mm]
> heißen =P ]
>
> Meine erste Frage wäre: Wann bzw. wie weiss ich, dass ein
> Kongruenzsystem modulo n eindeutig lösbar ist?
Es ist genau dann eindeutig loesbar, wenn es modulo jeder Primzahlpotenz [mm] $p^e$, [/mm] die $n$ teilt, eindeutig loesbar ist (hier kann $e$ maximal gewaehlt werden, also dass [mm] $p^e$ [/mm] $n$ teilt, [mm] $p^{e+1}$ [/mm] aber nicht mehr). Das folgt aus dem chinesischen Restsatz. (Den braucht man aber nur fuer eine Implikation.)
Modulo einer Primzahlpotenz sieht es nun so aus: so ein LGS ist modulo [mm] $p^e$ [/mm] genau dann eindeutig loesbar, wenn es modulo $p$ eindeutig loesbar ist. (Die eine Richtung ist wieder einfach. Fuer die andere Richtung zeigt man: hat man modulo [mm] $p^f$ [/mm] genau eine Loesung, so auch modulo [mm] $p^{f+1}$.)
[/mm]
Und modulo $p$ ist es genau dann eindeutig loesbar, wenn die Determinante der zugehoerigen Koeffizientenmatrix des LGS ungleich 0 ist. Modulo [mm] $p^e$ [/mm] bedeutet es also, dass die Determinante eine Einheit ist (also teilerfremd zu [mm] $p^e$).
[/mm]
Fasst man alles zusammen, so sieht man: ein LGS $A x = b$ ist modulo $n$ genau dann eindeutig loesbar, wenn $A$ quadratisch ist und [mm] $\det [/mm] A$ eine Einheit modulo $n$ ist (also teilerfremd zu $n$ ist).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:45 Sa 18.06.2011 | | Autor: | Hanz |
Vielen Dank für die sehr ausführliche Lösung!
|
|
|
|
