Chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:46 Mo 08.02.2010 | | Autor: | Liria |
| Aufgabe | Bestimme die modv 7 * 11 * 13 eindeutige Lösung des folgenden Systems simultaner Kongruenzen:
X [mm] \equiv [/mm] 2 mod 7
X [mm] \equiv [/mm] 3 mod 11
X [mm] \equiv [/mm] 4 mod 13. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Also ich habe den chin. Restsatz wie folgt gelernt, bzw folgende Lösungsansätze habe ich:
c1 = 2, c2 =3, c3 =4
m1 = 7, m2 = 11, m3 = 13
n1 = 143, n2 = 91, n3 = 77 (ni= m/mi)
Nun würde der erweiterte euklidsche Algorithmus kommen. Aber genau dieser ist mir im Zusammenhang mit dem chinesischen Restsatz nicht ganz klar. Ich weiß die allgemeine Formel ggT (a,b) = s * a + t * b.
Ich weiß auch das für X [mm] \equiv [/mm] 2 mod 7 gilt: s * 7 + t * 143 = 1
Doch mir will einfach nicht mehr einfallen wie man s und t in diesem Zusammenhang errechnet und auf das Ergebnis des Algorithmus kommt und wie man dann ni - 1 mod mi errechnet.
Wie man mit den Ergebnissen weiterhin verfährt ist mir dagegen wieder klar: c1 * n1 * (n1 - 1 mod m1) + ... + ci * ni * (ni- 1 mod mi).
Vielen Dank schon einmal für die Hilfe
|
|
| |
|
Hallo Liria,
> Bestimme die modv 7 * 11 * 13 eindeutige Lösung des
> folgenden Systems simultaner Kongruenzen:
> X [mm]\equiv[/mm] 2 mod 7
> X [mm]\equiv[/mm] 3 mod 11
> X [mm]\equiv[/mm] 4 mod 13.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Also ich habe den chin. Restsatz wie folgt gelernt, bzw
> folgende Lösungsansätze habe ich:
>
> c1 = 2, c2 =3, c3 =4
> m1 = 7, m2 = 11, m3 = 13
> n1 = 143, n2 = 91, n3 = 77 (ni= m/mi) ![[ok]](/images/smileys/ok.gif "[ok]")
>
> Nun würde der erweiterte euklidsche Algorithmus kommen.
> Aber genau dieser ist mir im Zusammenhang mit dem
> chinesischen Restsatz nicht ganz klar. Ich weiß die
> allgemeine Formel ggT (a,b) = s * a + t * b.
> Ich weiß auch das für X [mm]\equiv[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
2 mod 7 gilt: s * 7 + t *
> 143 = 1
> Doch mir will einfach nicht mehr einfallen wie man s und t
> in diesem Zusammenhang errechnet und auf das Ergebnis des
> Algorithmus kommt und wie man dann ni - 1 mod mi
> errechnet.
Ok, berechne nacheinander $\operatorname{ggT}(7,143), \operatorname{ggT}(11,91), \operatorname{ggT}(13,77)$ mit dem Euklidischen Algo.
$\operatorname{ggT}(7,143)=1$, denn:
$143=20\cdot{}7+3$
$7=2\cdot{}3+1$
$3=3\cdot{}1+0$
Also $\operatorname{ggT}(7,143)=1$
Nun Rückwärtseinsetzen, beginnend mit der vorletzten Zeile, in der ja der $\operatorname{ggT}$ steht
$1=7-2\cdot{}3$
Nun die 3 mit der Zeile darüber ersetzen:
$...=7-2\cdot{}(143-20\cdot{}7)=\red{-2\cdot{}143}+41\cdot{}7$
Also $\red{e_1=-286}$
Nun rechne die anderen $\operatorname{ggTs}$ analog aus und ebenso die entsprechenden LKen.
Dann ist die Lösung $x \ \equiv \ 2\cdot{}e_1+3}\cdot{}e_2+4\cdot{}e_3 \ \mod{\underbrace{1001}_{=\operatorname{kgV}(7,11,13)}$
>
> Wie man mit den Ergebnissen weiterhin verfährt ist mir
> dagegen wieder klar: c1 * n1 * (n1 - 1 mod m1) + ... + ci *
> ni * (ni- 1 mod mi).
>
> Vielen Dank schon einmal für die Hilfe
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:10 Mo 08.02.2010 | | Autor: | Liria |
*Ach patsch* Klar! Rückwärtseinsetzen! Darauf bin ich nicht gekommen. Vielen Dank für die rasche Antwort. War eine große Hilfe.
|
|
|
|
