Chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Lösen Sie mit dem Chinesischen Restsatz folgendes System von Kongruenzgleichungen:
$x [mm] \equiv [/mm] 1 [mm] (\mbox{mod } [/mm] 18)$
$x [mm] \equiv [/mm] 2 [mm] (\mbox{mod } [/mm] 5)$
$x [mm] \equiv [/mm] 9 [mm] (\mbox{mod } [/mm] 19)$
Hilfestellung:
Nach dem Chinesischen Restsatz hat das Gleichungssystem
$x [mm] \equiv b_{i}(\mbox{mod } m_{i})$
[/mm]
für $i [mm] \in \{1,...,n\}$ [/mm] eine eindeutige Lösung in [mm] $\IZ_{(m_{1}*...*m_{n})}$ [/mm] (also [mm] $\IZ$ [/mm] modulo dem Produkt aller [mm] $m_{i}$), [/mm] falls für beliebige $j,k [mm] \in \{1,...,n\}$ [/mm] jeweils [mm] $\mbox{ggT}(m_{i},m_{j})=1$ [/mm] gilt.
Eine Möglichkeit, ein solches Gleichungssystem zu lösen, geht wie folgt: Aus $x [mm] \equiv b_{1}(\mbox{mod } m_{1})$ [/mm] folgt, dass es ein $y [mm] \in \IZ$ [/mm] gibt mit [mm] $x=b_{1}+m_{1}*y$. [/mm] Dies können wir in die anderen Gleichungen einsetzen, also für $j [mm] \in \{2,...,n\}$ [/mm] haben wir dann [mm] $b_{1}+m_{1}*y \equiv b_{j}(\mbox{mod } m_{j})$. [/mm] Diese können wir umformen zu $y [mm] \equiv m_{1}^{-1} [/mm] * [mm] (b_{j}-b_{1})(\mbox{mod } m_{j})$, [/mm] wobei [mm] $m_{1}^{-1}$ [/mm] das Inverse zu [mm] $m_{1}$ [/mm] in [mm] $\IZ_{m}_{j}$ [/mm] ist, also zum Beispiel ist modulo 5 gerechnet 3 das Inverse zu 2, denn $2*3 = 6 [mm] \equiv [/mm] 1 [mm] (\mbox{mod } [/mm] 5)$. Damit haben wir nun n - 1 Gleichungen erhalten; und hätten wir eine Lösung für y bestimmt, so hätten wir auch sofort die Lösung für das ursprüngliche x durch die Gleichung $x = [mm] b_{1} [/mm] + [mm] m_{1}*y$. [/mm] Damit können wir x bestimmen, in dem wir diesen Schritt so lange wiederholen, bis nur noch eine Gleichung übriggeblieben ist. |
Hallo,
mein Problem bei dieser Aufgabe ist der 2. Schritt in der
Musterlösung:
Im ersten Schritt haben wir x = 1 + 18y, also
$y [mm] \equiv [/mm] 2(2-1) [mm] \equiv [/mm] 2 [mm] (\mbox{mod } [/mm] 5)$
$y [mm] \equiv [/mm] 18(9-1) [mm] \equiv [/mm] 11 [mm] (\mbox{mod } [/mm] 19)$
und im zweiten Schritt dann y = 2 + 5z so wie
$z [mm] \equiv [/mm] 4(11-2) [mm] \equiv [/mm] 17 [mm] (\mbox{mod }19)$
[/mm]
Damit erhalten wir z = 17, y = 87 und x = 1567 wie benötigt.
Weiß jemand, wie das y und das z im 2. Schritt zustande kommen?
Vielen Dank für die Mühe (sorry, dass das soviel zum Lesen ist)!
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:58 Do 12.07.2012 | | Autor: | hippias |
> Lösen Sie mit dem Chinesischen Restsatz folgendes System
> von Kongruenzgleichungen:
>
> [mm]x \equiv 1 (\mbox{mod } 18)[/mm]
> [mm]x \equiv 2 (\mbox{mod } 5)[/mm]
> [mm]x \equiv 9 (\mbox{mod } 19)[/mm]
>
> Hilfestellung:
> Nach dem Chinesischen Restsatz hat das Gleichungssystem
>
> [mm]x \equiv b_{i}(\mbox{mod } m_{i})[/mm]
>
> für [mm]i \in \{1,...,n\}[/mm] eine eindeutige Lösung in
> [mm]\IZ_{(m_{1}*...*m_{n})}[/mm] (also [mm]\IZ[/mm] modulo dem Produkt aller
> [mm]m_{i}[/mm]), falls für beliebige [mm]j,k \in \{1,...,n\}[/mm] jeweils
> [mm]\mbox{ggT}(m_{i},m_{j})=1[/mm] gilt.
> Eine Möglichkeit, ein solches Gleichungssystem zu lösen,
> geht wie folgt: Aus [mm]x \equiv b_{1}(\mbox{mod } m_{1})[/mm]
> folgt, dass es ein [mm]y \in \IZ[/mm] gibt mit [mm]x=b_{1}+m_{1}*y[/mm]. Dies
> können wir in die anderen Gleichungen einsetzen, also für
> [mm]j \in \{2,...,n\}[/mm] haben wir dann [mm]b_{1}+m_{1}*y \equiv b_{j}(\mbox{mod } m_{j})[/mm].
> Diese können wir umformen zu [mm]y \equiv m_{1}^{-1} * (b_{j}-b_{1})(\mbox{mod } m_{j})[/mm],
> wobei [mm]m_{1}^{-1}[/mm] das Inverse zu [mm]m_{1}[/mm] in [mm]\IZ_{m}_{j}[/mm] ist,
> also zum Beispiel ist modulo 5 gerechnet 3 das Inverse zu
> 2, denn [mm]2*3 = 6 \equiv 1 (\mbox{mod } 5)[/mm]. Damit haben wir
> nun n - 1 Gleichungen erhalten; und hätten wir eine
> Lösung für y bestimmt, so hätten wir auch sofort die
> Lösung für das ursprüngliche x durch die Gleichung [mm]x = b_{1} + m_{1}*y[/mm].
> Damit können wir x bestimmen, in dem wir diesen Schritt so
> lange wiederholen, bis nur noch eine Gleichung
> übriggeblieben ist.
> Hallo,
>
> mein Problem bei dieser Aufgabe ist der 2. Schritt in der
>
> Musterlösung:
> Im ersten Schritt haben wir x = 1 + 18y, also
>
> [mm]y \equiv 2(2-1) \equiv 2 (\mbox{mod } 5)[/mm]
> [mm]y \equiv 18(9-1) \equiv 11 (\mbox{mod } 19)[/mm]
>
> und im zweiten Schritt dann y = 2 + 5z so wie
>
> [mm]z \equiv 4(11-2) \equiv 17 (\mbox{mod }19)[/mm]
>
> Damit erhalten wir z = 17, y = 87 und x = 1567 wie
> benötigt.
>
>
>
> Weiß jemand, wie das y und das z im 2. Schritt zustande
> kommen?
Es gilt $x= 1+18y$, wobei auch [mm] $x\equiv [/mm] 2$ mod $5$. Einsetzen liefert [mm] $1+18y\equiv [/mm] 2$ mod $5$. Formt man jetz nach $y$ um,so muss an einer Stelle mit dem Inversen modulo $5$ von $18$ multipliziert werden: diese ist kongruent $2$ modulo $5$; daher die Multiplikation mit $2$.
>
> Vielen Dank für die Mühe (sorry, dass das soviel zum
> Lesen ist)!
Kein Thema.
>
>
> Gruß
> el_grecco
>
|
|
|
| |
|
Hallo hippias,
ich glaube es liegt ein Missverständnis vor: ich meinte den zweiten Schritt nach der Zählweise der Musterlösung, also die beiden Gleichungen
y = 2 + 5z
$z [mm] \equiv [/mm] 4(11-2) [mm] \equiv [/mm] 17 [mm] (\mbox{mod }19)$
[/mm]
Leider habe ich da noch immer Probleme. Ich stelle die Frage deshalb auf "noch nicht beantwortet".
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:02 Do 12.07.2012 | | Autor: | hippias |
> Hallo hippias,
>
> ich glaube es liegt ein Missverständnis vor: ich meinte
> den zweiten Schritt nach der Zählweise der Musterlösung,
> also die beiden Gleichungen
>
> y = 2 + 5z
Ich bin mir nicht sicher, ob ich Deine Frage jetzt besser verstanden habe: Also [mm] $1+18y\equiv_{5} [/mm] 2$ war klar? Dann folgt [mm] $y\equiv_{5} 2(2-1)\equiv_{5} [/mm] 2$. Anders ausgedrueckt heisst das, dass es ein [mm] $z\in\IZ$ [/mm] gibt, sodass $y= 2+ 5z$. Diesen Ausdruck kannst Du jetzt wieder in der Gleichung fuer $x$ einfuegen und die analogen Rechenschritte mit der dritten Kongruenz durchfuehren, um etwas ueber das $z$ herauszufinden. Ich hoffe, das hilft.
>
> [mm]z \equiv 4(11-2) \equiv 17 (\mbox{mod }19)[/mm]
>
>
> Leider habe ich da noch immer Probleme. Ich stelle die
> Frage deshalb auf "noch nicht beantwortet".
>
> Gruß
> el_grecco
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:13 Do 12.07.2012 | | Autor: | el_grecco |
Hallo hippias,
> > Hallo hippias,
> >
> > ich glaube es liegt ein Missverständnis vor: ich meinte
> > den zweiten Schritt nach der Zählweise der Musterlösung,
> > also die beiden Gleichungen
> >
> > y = 2 + 5z
> Ich bin mir nicht sicher, ob ich Deine Frage jetzt besser
> verstanden habe: Also [mm]1+18y\equiv_{5} 2[/mm] war klar? Dann
> folgt [mm]y\equiv_{5} 2(2-1)\equiv_{5} 2[/mm]. Anders ausgedrueckt
> heisst das, dass es ein [mm]z\in\IZ[/mm] gibt, sodass [mm]y= 2+ 5z[/mm].
> Diesen Ausdruck kannst Du jetzt wieder in der Gleichung
> fuer [mm]x[/mm] einfuegen und die analogen Rechenschritte mit der
> dritten Kongruenz durchfuehren, um etwas ueber das [mm]z[/mm]
> herauszufinden. Ich hoffe, das hilft.
> >
genau das meinte ich.
Jetzt habe ich es aber verstanden und der Thread kann als "erledigt" markiert werden - Danke Dir! 
> > [mm]z \equiv 4(11-2) \equiv 17 (\mbox{mod }19)[/mm]
> >
> >
> > Leider habe ich da noch immer Probleme. Ich stelle die
> > Frage deshalb auf "noch nicht beantwortet".
> >
Gruß
el_grecco
|
|
|
|
