Chinesischer Restsatz < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:13 Do 08.01.2015 | | Autor: | xx_xx_xx |
| Aufgabe | Bestimmen Sie alle Lösungen:
X [mm] \equiv [/mm] 1 (mod 5)
X [mm] \equiv [/mm] 5 (mod 6)
X [mm] \equiv [/mm] 8 (mod 15) |
Hallo!
Also ich bin mir recht sicher, dass es nicht lösbar ist, bin mir aber nicht sicher warum bzw wie ich es begründe
X [mm] \equiv [/mm] 1 (mod 5)
X [mm] \equiv [/mm] 5 (mod 6) [mm] \gdw [/mm] X [mm] \equiv [/mm] 1 (mod 2) [mm] \wedge [/mm] X [mm] \equiv [/mm] 2 (mod 3)
X [mm] \equiv [/mm] 8 (mod 15) [mm] \gdw [/mm] X [mm] \equiv [/mm] 2 (mod 3) [mm] \wedge [/mm] X [mm] \equiv [/mm] 3 (mod 5)
Also:
X [mm] \equiv [/mm] 1 (mod 5)
X [mm] \equiv [/mm] 3 (mod 5)
X [mm] \equiv [/mm] 1 (mod 2)
X [mm] \equiv [/mm] 2 (mod 3)
Wie gehe ich jetzt weiter vor?
Danke!
VG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:31 Do 08.01.2015 | | Autor: | Marcel |
Hallo,
> Bestimmen Sie alle Lösungen:
>
> X [mm]\equiv[/mm] 1 (mod 5)
> X [mm]\equiv[/mm] 5 (mod 6)
> X [mm]\equiv[/mm] 8 (mod 15)
> Hallo!
>
> Also ich bin mir recht sicher, dass es nicht lösbar ist,
> bin mir aber nicht sicher warum
das ist mal 'ne interessante Frage: Warum begründe ich das überhaupt? ![[grins]](/images/smileys/grins.gif "[grins]")
> bzw wie ich es begründe
>
> X [mm]\equiv[/mm] 1 (mod 5)
>
> X [mm]\equiv[/mm] 5 (mod 6) [mm]\gdw[/mm] X [mm]\equiv[/mm] 1 (mod 2) [mm]\wedge[/mm] X
> [mm]\equiv[/mm] 2 (mod 3)
>
> X [mm]\equiv[/mm] 8 (mod 15) [mm]\gdw[/mm] X [mm]\equiv[/mm] 2 (mod 3) [mm]\wedge[/mm] X
> [mm]\equiv[/mm] 3 (mod 5)
>
> Also:
>
> X [mm]\equiv[/mm] 1 (mod 5)
> X [mm]\equiv[/mm] 3 (mod 5)
> X [mm]\equiv[/mm] 1 (mod 2)
> X [mm]\equiv[/mm] 2 (mod 3)
>
> Wie gehe ich jetzt weiter vor?
Ich wäre das anders angegangen, aber ich benutze den Chinesischen
Restsatz auch in folgender Version:
Gegeben seien $a,b [mm] \in \IZ$ [/mm] und $n,m [mm] \in \IN.$ [/mm] Sei [mm] $d:=\ggT(n,m)$ [/mm] und $y,z [mm] \in \IZ$ [/mm] so,
dass [mm] $yn+zm=d=\ggT(n,m).$ [/mm] Die simultanen Kongruenzen
$x [mm] \equiv [/mm] a [mm] \mod [/mm] n$ und $x [mm] \equiv [/mm] b [mm] \mod [/mm] m$
sind genau dann lösbar, wenn $a [mm] \equiv [/mm] b [mm] \mod [/mm] d$. Im Falle der Lösbarkeit ist
das System der simultanen Kongruenzen äquivalent zu
$x [mm] \equiv [/mm] a - [mm] yn\frac{a-b}{d} \mod \frac{mn}{d}\,.$
[/mm]
(Satz 4.11 in "Elementare und algebraische Zahlentheorie, Müller-Stach, P.";
Chinesischer Restsatz, 1. Version!)
Schauen wir mal:
$x [mm] \equiv [/mm] 1 [mm] \mod [/mm] 5$ und $x [mm] \equiv [/mm] 5 [mm] \mod [/mm] 6.$
Wende den Satz an (beachte [mm] $-1*5+1*6=1=\ggT(5,6)$), [/mm] und wir haben die
äquivalente Kongr. (beachte a=1, n=5, b=5, m=6 in obigem Satz; weiter y=-1, z=1)
$x [mm] \equiv 1-(-1)*5*\frac{1-5}{1} \mod \frac{5*6}{1}$
[/mm]
[mm] $\iff$
[/mm]
$x [mm] \equiv [/mm] -19 [mm] \equiv [/mm] 11 [mm] \mod 30\,.$
[/mm]
Wir haben nun also das zum Ausgangssystem äquivalente System
$x [mm] \equiv [/mm] 11 [mm] \mod [/mm] 30$ und $x [mm] \equiv [/mm] 8 [mm] \mod [/mm] 15$.
Jetzt haben wir, wenn wir "die alten Variablen löschen", den Satz also anzuwenden
für
a=11, n=30, b=8 und m=15.
Wegen [mm] $\ggT(n,m)=\ggT(30,15)=15 \nmid [/mm] a-b=11-8=3$ ist dieses System simultaner
Kongrunzen nicht lösbar.
(Beachte: $r [mm] \equiv [/mm] s [mm] \mod \ell$ $\iff$ $\ell \mid [/mm] (r-s)$ [mm] $\iff$ $\ell \mid [/mm] (s-r).$)
P.S. Die $y,z [mm] \in \IZ$ [/mm] mit [mm] $\ggT(n,m)=d=yn+zm$ [/mm] findest Du i.A. etwa mit dem
erweiterten euklidischen Algorithmus!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:56 Do 08.01.2015 | | Autor: | xx_xx_xx |
| Aufgabe | Bestimmen Sie die Lösungen:
X [mm] \equiv [/mm] 33 (mod 34)
2X [mm] \equiv [/mm] -3 (mod 5)
3X [mm] \equiv [/mm] 5 (mod 7) |
Danke! Die erste Aufgabe habe ich verstanden!
Ich habe aber jetzt noch eine zweite Aufgabe und weiß hier leider nicht, was ich mit den Vorfaktoren 2 und 3 machen soll...
Ich habe nur eine Lösung für
X [mm] \equiv [/mm] 33 (mod 34)
X [mm] \equiv [/mm] -3 (mod 5)
X [mm] \equiv [/mm] 5 (mod 7)
[mm] \Rightarrow \IL={747 (mod 1190)}
[/mm]
aber das bringt mir auch nichts, richtig?
Wäre super, wenn mir jemand helfen könnte...
Danke!
VG
|
|
|
| |
|
Hallo,
> Bestimmen Sie die Lösungen:
>
> X [mm]\equiv[/mm] 33 (mod 34)
> 2X [mm]\equiv[/mm] -3 (mod 5)
> 3X [mm]\equiv[/mm] 5 (mod 7)
> Danke! Die erste Aufgabe habe ich verstanden!
>
> Ich habe aber jetzt noch eine zweite Aufgabe und weiß hier
> leider nicht, was ich mit den Vorfaktoren 2 und 3 machen
> soll...
Schreiben wir die letzten beiden Gleichungen doch mal um:
2X [mm]\equiv[/mm] -3 (mod 5)
[mm] \gdw \overline{2X} [/mm] = [mm] \overline{-3} \in \IZ_{5} [/mm]
[mm] \gdw \overline{2X} [/mm] = [mm] \overline{2} \in \IZ_{5} [/mm]
Nun multipilizieren mit dem Inversen zu [mm] \overline{2} \in \IZ_{5}, [/mm] also [mm] \overline{3}. [/mm] Das führt zu:
[mm] \gdw \overline{3*2X} [/mm] = [mm] \overline{3*2} \in \IZ_{5}
[/mm]
[mm] \gdw \overline{6X} [/mm] = [mm] \overline{6} \in \IZ_{5}
[/mm]
[mm] \gdw \overline{X} [/mm] = [mm] \overline{1} \in \IZ_{5}
[/mm]
[mm] \gdw [/mm] X [mm]\equiv[/mm] 1 (mod 5)
Analog ist:
3X [mm]\equiv[/mm] 5 (mod 7)
[mm] \gdw \overline{3X} [/mm] = [mm] \overline{5} \in \IZ_{7}
[/mm]
Mit dem Inversen zu [mm] \overline{3} \in \IZ_{7} [/mm] multiplizieren, also [mm] \overline{5}, [/mm] führt zu:
[mm] \gdw \overline{5*3X} [/mm] = [mm] \overline{5*5} \in \IZ_{7}
[/mm]
[mm] \gdw \overline{15X} [/mm] = [mm] \overline{25} \in \IZ_{7}
[/mm]
[mm] \gdw \overline{X} [/mm] = [mm] \overline{4} \in \IZ_{7}
[/mm]
[mm] \gdw [/mm] X [mm]\equiv[/mm] 4 (mod 7).
Nun musst nur noch das Kongruenzgleichungssystem lösen:
X [mm]\equiv[/mm] 33 (mod 34)
X [mm]\equiv[/mm] 1 (mod 5)
X [mm]\equiv[/mm] 4 (mod 7)
Viele Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:26 Do 08.01.2015 | | Autor: | xx_xx_xx |
Toll!
Vielen, vielen Dank!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:45 Do 08.01.2015 | | Autor: | Marcel |
Hallo,
> Bestimmen Sie die Lösungen:
>
> X [mm]\equiv[/mm] 33 (mod 34)
> 2X [mm]\equiv[/mm] -3 (mod 5)
> 3X [mm]\equiv[/mm] 5 (mod 7)
> Danke! Die erste Aufgabe habe ich verstanden!
>
> Ich habe aber jetzt noch eine zweite Aufgabe und weiß hier
> leider nicht, was ich mit den Vorfaktoren 2 und 3 machen
> soll...
neben dem Gesagten gibt es auch hier wieder einen Satz aus dem Buch
"Elementare und algebraische Zahlentheorie". (Satz 4.8)
Die Kongruenz
$ax [mm] \equiv [/mm] b [mm] \mod [/mm] n$ mit $a,b [mm] \in \IZ$ [/mm] und $n [mm] \in \IN$
[/mm]
ist genau dann lösbar, wenn mit [mm] $d:=\ggT(a,n)$ [/mm] gilt $d [mm] \mid b\,.$ [/mm] Im Falle der Lösbarkeit
ist sie gleichwertig zu
$x [mm] \equiv [/mm] y [mm] \frac{b}{d} \mod \frac{n}{d}\,,$
[/mm]
wobei $y,z [mm] \in \IZ$ [/mm] mit [mm] $d=\ggT(a,n)=ya+zn\,.$
[/mm]
Gruß,
Marcel
|
|
|
| |
|
Hallo,
> Bestimmen Sie alle Lösungen:
>
> X [mm]\equiv[/mm] 1 (mod 5)
> X [mm]\equiv[/mm] 5 (mod 6)
> X [mm]\equiv[/mm] 8 (mod 15)
> Hallo!
>
> Also ich bin mir recht sicher, dass es nicht lösbar ist,
> bin mir aber nicht sicher warum bzw wie ich es begründe
>
> X [mm]\equiv[/mm] 1 (mod 5)
>
> X [mm]\equiv[/mm] 5 (mod 6) [mm]\gdw[/mm] X [mm]\equiv[/mm] 1 (mod 2) [mm]\wedge[/mm] X
> [mm]\equiv[/mm] 2 (mod 3)
>
> X [mm]\equiv[/mm] 8 (mod 15) [mm]\gdw[/mm] X [mm]\equiv[/mm] 2 (mod 3) [mm]\wedge[/mm] X
> [mm]\equiv[/mm] 3 (mod 5)
>
> Also:
>
> X [mm]\equiv[/mm] 1 (mod 5)
> X [mm]\equiv[/mm] 3 (mod 5)
> X [mm]\equiv[/mm] 1 (mod 2)
> X [mm]\equiv[/mm] 2 (mod 3)
>
Naja, wie kann eine Zahl denn gleichzeitig 1(mod 5) und 3 (mod 5) sein...? Geht nicht, denn Sie kann nur eins von beidem sein!
Viele Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:48 Do 08.01.2015 | | Autor: | Marcel |
Hallo,
> Hallo,
> > Bestimmen Sie alle Lösungen:
> >
> > X [mm]\equiv[/mm] 1 (mod 5)
> > X [mm]\equiv[/mm] 5 (mod 6)
> > X [mm]\equiv[/mm] 8 (mod 15)
> > Hallo!
> >
> > Also ich bin mir recht sicher, dass es nicht lösbar ist,
> > bin mir aber nicht sicher warum bzw wie ich es begründe
> >
> > X [mm]\equiv[/mm] 1 (mod 5)
> >
> > X [mm]\equiv[/mm] 5 (mod 6) [mm]\gdw[/mm] X [mm]\equiv[/mm] 1 (mod 2) [mm]\wedge[/mm] X
> > [mm]\equiv[/mm] 2 (mod 3)
> >
> > X [mm]\equiv[/mm] 8 (mod 15) [mm]\gdw[/mm] X [mm]\equiv[/mm] 2 (mod 3) [mm]\wedge[/mm] X
> > [mm]\equiv[/mm] 3 (mod 5)
> >
> > Also:
> >
> > X [mm]\equiv[/mm] 1 (mod 5)
> > X [mm]\equiv[/mm] 3 (mod 5)
> > X [mm]\equiv[/mm] 1 (mod 2)
> > X [mm]\equiv[/mm] 2 (mod 3)
> >
> Naja, wie kann eine Zahl denn gleichzeitig 1(mod 5) und 3
> (mod 5) sein...? Geht nicht, denn Sie kann nur eins von
> beidem sein!
das ist natürlich auch eine gute Begründung (anders gesagt:
[mm] $[1]_5 \not= [3]_5$).
[/mm]
Gruß,
Marcel
|
|
|
|
