Chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:15 Fr 23.05.2014 | | Autor: | xx_xx_xx |
| Aufgabe | Das folgende System simultaner Kongruenzen ist zum beispiel für c=7 offensichtlich lösbar
x [mm] \equiv [/mm] 7 (mod 51)
x [mm] \equiv [/mm] c (mod 42)
Bestimme alle c [mm] \in \IZ, [/mm] sodass eine Lösung existiert und bestimme eine Lösung für das betragsmäßig kleinste gefundene c [mm] \in \IN [/mm] |
Hallo,
also ich kann das System ja auch in folgenden umwandeln:
x [mm] \equiv [/mm] 7 (mod 3) [mm] \gdw [/mm] x [mm] \equiv [/mm] 1 (mod 3)
x [mm] \equiv [/mm] 7 (mod 17)
x [mm] \equiv [/mm] c (mod 3)
x [mm] \equiv [/mm] c (mod 2)
x [mm] \equiv [/mm] c (mod 7)
daraus kann ich schließen, dass c die Form c=a*3+1 hat, a [mm] \in \IN [/mm]
Ich müsste jetzt ja sozusagen eine von dem (mod 3) "wegbekommen", aber wie mache ich dass, kann ich die erste weglassen und dann c als a*3+1 schreiben, also folgende benutzen:
x [mm] \equiv [/mm] 7 (mod 17)
x [mm] \equiv [/mm] a*3+1 (mod 3)
x [mm] \equiv [/mm] a*3+1 (mod 2)
x [mm] \equiv [/mm] a*3+1 (mod 7)
?
Viele Dank schonmal für die Hilfe!
|
|
| |
|
Hallo,
das sieht soweit gut aus.
> Das folgende System simultaner Kongruenzen ist zum beispiel
> für c=7 offensichtlich lösbar
>
> x [mm]\equiv[/mm] 7 (mod 51)
> x [mm]\equiv[/mm] c (mod 42)
>
> Bestimme alle c [mm]\in \IZ,[/mm] sodass eine Lösung existiert und
> bestimme eine Lösung für das betragsmäßig kleinste
> gefundene c [mm]\in \IN[/mm]
> Hallo,
>
> also ich kann das System ja auch in folgenden umwandeln:
>
> x [mm]\equiv[/mm] 7 (mod 3) [mm]\gdw[/mm] x [mm]\equiv[/mm] 1 (mod 3)
> x [mm]\equiv[/mm] 7 (mod 17)
> x [mm]\equiv[/mm] c (mod 3)
> x [mm]\equiv[/mm] c (mod 2)
> x [mm]\equiv[/mm] c (mod 7)
>
> daraus kann ich schließen, dass c die Form c=a*3+1 hat, a
> [mm]\in \IN[/mm]
>
> Ich müsste jetzt ja sozusagen eine von dem (mod 3)
> "wegbekommen", aber wie mache ich dass, kann ich die erste
> weglassen und dann c als a*3+1 schreiben, also folgende
> benutzen:
>
> x [mm]\equiv[/mm] 7 (mod 17)
> x [mm]\equiv[/mm] a*3+1 (mod 3)
> x [mm]\equiv[/mm] a*3+1 (mod 2)
> x [mm]\equiv[/mm] a*3+1 (mod 7)
>
> ?
Ja, das geht. Besser ist aber, Du lässt die andere Kongruenz mod 3 weg, denn die jetzt hier steht, ist dazu äquivalent. Du hast also nur [mm] x\equiv 1\bmod{3}.
[/mm]
Als nächstes sollst Du feststellen, dass das System für jedes $a$ lösbar ist. Das betragsmäßig kleinste [mm] c\in\IZ [/mm] ist also $c=1$, die gesuchte Lösung ist [mm] x\equiv 211\bmod{714}.
[/mm]
Du musst nur noch den Weg finden, aber die Zwischenergebnisse der einzelnen Schritte hast Du jetzt.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:39 Fr 23.05.2014 | | Autor: | abakus |
> Das folgende System simultaner Kongruenzen ist zum beispiel
> für c=7 offensichtlich lösbar
>
> x [mm]\equiv[/mm] 7 (mod 51)
> x [mm]\equiv[/mm] c (mod 42)
>
> Bestimme alle c [mm]\in \IZ,[/mm] sodass eine Lösung existiert und
> bestimme eine Lösung für das betragsmäßig kleinste
> gefundene c [mm]\in \IN[/mm]
> Hallo,
>
> also ich kann das System ja auch in folgenden umwandeln:
>
> x [mm]\equiv[/mm] 7 (mod 3) [mm]\gdw[/mm] x [mm]\equiv[/mm] 1 (mod 3)
> x [mm]\equiv[/mm] 7 (mod 17)
> x [mm]\equiv[/mm] c (mod 3)
> x [mm]\equiv[/mm] c (mod 2)
> x [mm]\equiv[/mm] c (mod 7)
>
> daraus kann ich schließen, dass c die Form c=a*3+1 hat, a
> [mm]\in \IN[/mm]
>
> Ich müsste jetzt ja sozusagen eine von dem (mod 3)
> "wegbekommen", aber wie mache ich dass, kann ich die erste
> weglassen und dann c als a*3+1 schreiben, also folgende
> benutzen:
>
> x [mm]\equiv[/mm] 7 (mod 17)
> x [mm]\equiv[/mm] a*3+1 (mod 3)
> x [mm]\equiv[/mm] a*3+1 (mod 2)
> x [mm]\equiv[/mm] a*3+1 (mod 7)
>
> ?
>
> Viele Dank schonmal für die Hilfe!
Hallo,
du kannst auch ohne Kongruenzen umformulieren in:
x=51k+7 und x=42n+c (mit ganzzahligen Faktoren k und n).
Gleichsetzen liefert 51k+7=42n+c bzw.
51k-42n=c-7
Links wird der ggT ausgeklammert:
3(17k-14n)=c-7.
Das ist nur lösbar, wenn c-7 durch 3 teilbar ist.
Das betragsmäßig kleinste c für diese Forderung ist c=1.
Nun zeige noch, dass für jeden durch 3 teilbaren Wert von (c-7) auch ein entsprechendes Paar von Faktoren (k;n) existiert, das diese Gleichung erfüllt.
Gruß Abakus
|
|
|
|
