Systeme von Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:23 Do 22.01.2009 | | Autor: | mimi1310 |
| Aufgabe | Seien n1, n2 [mm] \ge [/mm] 1 und a1, a2, b1, b2 [mm] \in \IZ [/mm] mit a1 [mm] \not= [/mm] 0 und a2 [mm] \not= [/mm] 0. Ferner sei [mm] x_{0} \in \IZ [/mm] mit [mm] a1x_{0} \equiv [/mm] b1 mod n1 und [mm] a2x_{0} \equiv [/mm] b2 mod n2.
Man gebe alle Lösungen x des Systems a1x [mm] \equiv [/mm] b1 mod n1 und a2x [mm] \equiv [/mm] b2 mod n2 an. |
Das grundsätzliche Verfahren ist mir klar und auch Beispielaufgaben zu rechnen ist kein Problem. Mir ist aber nicht klar, wie ich hier herangehen muss. Wie kriege ich denn erstmal das a1 bzw. das a2 vor dem x weg und wie kriege ich dann alle Lösungen?
|
|
| |
|
Hallo mimi,
das ist in der Tat ein bisschen blöd...
Fallunterscheidung:
1) [mm] ggT(a_1,n_1)=1
[/mm]
Dann existiert ein [mm] \overline{a}_1 [/mm] mit [mm] a_1*\overline{a}_1\equiv 1\mod{n_1} [/mm] ...
2) [mm] ggT(a_1,n_1)=t_1
[/mm]
Dann teilt [mm] t_1 [/mm] auch [mm] b_1 [/mm] und die Äquivalenz lässt sich so umformen, dass die Existenz von [mm] \hat{a}_1 [/mm] mit [mm] a_1*\hat{a}_1\equiv b_1\mod{n_1} [/mm] zu zeigen ist.
Genauso für [mm] n_2. [/mm] Lösung dann mit dem chinesischen Restesatz, wieder mit Fallunterscheidung nach [mm] ggT(n_1,n_2).
[/mm]
So müsste es gehen, denke ich.
lg,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:54 Do 22.01.2009 | | Autor: | mimi1310 |
Hallo!
Erstmal vielen vielen Dank, nur habe ich jetzt noch eine (vielleicht etwas blöde) Frage, ich stehe bei dieser Aufgabe nämlich irgend wie völlig auf dem Schlauch.... um die Formel des chinesischen Restsatzen anwenden zu können muss ich doch immer das x alleine stehen haben oder? Also [mm] x\equiv [/mm] .... mod n1 und wie komme ich denn jetzt zu dieser Form? Klar, dass ich erstmal prüfen muss ob die Kongruenz überhaupt lösbar ist aber dann...?
|
|
|
| |
|
Na, über die Multiplikation mit [mm] \overline{a}_1 [/mm] bzw. [mm] \hat{a}_1 [/mm] (siehe letzte Antwort), wobei der zweite Fall etwas mehr Überlegung erfordert.
In der Tat musst Du normalerweise für die Anwendung des "Chinesen" vor dem x den Faktor 1 haben. Das ist aber andererseits nicht zwingend nötig, es vereinfacht das Finden einer Lösung eines Systems von Kongruenzen nur erheblich. Der Satz besagt ja im wesentlichen, dass Du mit einer Lösung schon alle gefunden hast.
|
|
|
|
