Chinesischer Restsatz < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:31 Mo 30.03.2015 | | Autor: | KilaZ |
| Aufgabe | [mm] x\equiv1 [/mm] mod 5 [mm] x\equiv0 [/mm] mod 8
[mm] x\equiv2 [/mm] mod 7 [mm] x\equiv3 [/mm] mod11 |
Hi,
ich soll die Aufgabe mithilfe des chinesischen Restsatz berechnen.
Laut Skriptum funtioniert dies so: [mm] x=\summe_{i=1}^{s}c_{i}a_{i}\bruch{m}{m_{i}}
[/mm]
Wobei [mm] c_{1}=1, c_{2}=2, c_{3}=0, c_{4}=3 [/mm] und [mm] m_{1}=5, m_{2}=7, m_{3}=8, m_{4}=11 [/mm] und m=5*7*8*11=3080
Die [mm] a_{i} [/mm] bekomme ich vom erweiterten Euklid.
[mm] ggT(m_{i}, \bruch{m}{m_{i}})=a*m+b*n
[/mm]
ggT(5, [mm] \bruch{3080}{5})=ggT(5, [/mm] 616)=1=1*616-123*5
ggT(7, 440)=1=-1*440+63*7
ggT(8, 385)=1=1*385-48*8
ggT(11, 280)=1=-2*280+51*11
und deshalb laut Formel: 1*1*616+2*(-1)*440+0*1*385+3*(-2)*280=-1944
was nicht stimmen kann.
Doch wo ist mein Fehler? Den erweiterten Euklid habe ich per Online-Rechner überprüft und der Rest sollte doch passen?
Gruss
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:51 Di 31.03.2015 | | Autor: | Marcel |
Hallo,
> [mm]x\equiv1[/mm] mod 5 [mm]x\equiv0[/mm] mod 8
> [mm]x\equiv2[/mm] mod 7 [mm]x\equiv3[/mm] mod11
>
> Hi,
>
> ich soll die Aufgabe mithilfe des chinesischen Restsatz
> berechnen.
> Laut Skriptum funtioniert dies so:
> [mm]x=\summe_{i=1}^{s}c_{i}a_{i}\bruch{m}{m_{i}}[/mm]
>
> Wobei [mm]c_{1}=1, c_{2}=2, c_{3}=0, c_{4}=3[/mm] und [mm]m_{1}=5, m_{2}=7, m_{3}=8, m_{4}=11[/mm]
> und m=5*7*8*11=3080
>
> Die [mm]a_{i}[/mm] bekomme ich vom erweiterten Euklid.
> [mm]ggT(m_{i}, \bruch{m}{m_{i}})=a*m+b*n[/mm]
>
> ggT(5, [mm]\bruch{3080}{5})=ggT(5,[/mm] 616)=1=1*616-123*5
> ggT(7, 440)=1=-1*440+63*7
> ggT(8, 385)=1=1*385-48*8
> ggT(11, 280)=1=-2*280+51*11
>
> und deshalb laut Formel:
> 1*1*616+2*(-1)*440+0*1*385+3*(-2)*280=-1944
> was nicht stimmen kann.
wieso nicht?
1.) $-1944=-389*5+1$
2.) $-1944=-243*8+0$
3.) $-1944=-278*7+2$
4.) $-1944=-177*11+3$
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:55 Di 31.03.2015 | | Autor: | Marcel |
P.S. > [mm]x\equiv1[/mm] mod 5 [mm]x\equiv0[/mm] mod 8
> [mm]x\equiv2[/mm] mod 7 [mm]x\equiv3[/mm] mod11
>
> Hi,
>
> ich soll die Aufgabe mithilfe des chinesischen Restsatz
> berechnen.
> Laut Skriptum funtioniert dies so:
> [mm]x=\summe_{i=1}^{s}c_{i}a_{i}\bruch{m}{m_{i}}[/mm]
>
> Wobei [mm]c_{1}=1, c_{2}=2, c_{3}=0, c_{4}=3[/mm] und [mm]m_{1}=5, m_{2}=7, m_{3}=8, m_{4}=11[/mm]
> und m=5*7*8*11=3080
>
> Die [mm]a_{i}[/mm] bekomme ich vom erweiterten Euklid.
> [mm]ggT(m_{i}, \bruch{m}{m_{i}})=a*m+b*n[/mm]
>
> ggT(5, [mm]\bruch{3080}{5})=ggT(5,[/mm] 616)=1=1*616-123*5
> ggT(7, 440)=1=-1*440+63*7
> ggT(8, 385)=1=1*385-48*8
> ggT(11, 280)=1=-2*280+51*11
>
> und deshalb laut Formel:
> 1*1*616+2*(-1)*440+0*1*385+3*(-2)*280=-1944
> was nicht stimmen kann.
Du könntest übrigens auch
[mm] $\,5*7*8*11-1944=1136\,$
[/mm]
betrachten.
P.P.S. Erinnere Dich vielleicht auch daran, dass sowas wie
$-4 [mm] \equiv [/mm] 1 [mm] \mod [/mm] 5$
(hier allgemeiner: $1 [mm] \equiv [/mm] 1+k*5 [mm] \mod [/mm] 5$ für alle $k [mm] \in \IZ$)
[/mm]
gilt.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:14 Mi 01.04.2015 | | Autor: | KilaZ |
Hi,
danke - dann habe ich es bei diesem Beispiel verstanden!
Noch eine Frage zu diesem Bsp.:
[mm] x\equiv1 [/mm] mod 3 [mm] x\equiv3 [/mm] mod 9 [mm] x\equiv2 [/mm] mod 10
Kann ich sagen, dass hier der chinesische Restsatz nicht moeglich ist, da die Moduln nicht teilerfremd sind?
Gruss
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:34 Mi 01.04.2015 | | Autor: | Marcel |
Hallo,
> Hi,
>
> danke - dann habe ich es bei diesem Beispiel verstanden!
> Noch eine Frage zu diesem Bsp.:
> [mm]x\equiv1[/mm] mod 3 [mm]x\equiv3[/mm] mod 9 [mm]x\equiv2[/mm] mod 10
>
> Kann ich sagen, dass hier der chinesische Restsatz nicht
> moeglich ist, da die Moduln nicht teilerfremd sind?
wenn ihr den nur so formuliert habt, kannst Du natürlich Eure Version nicht
anwenden oder musst ein wenig tricksen, bis er anwendbar wird.
Lies auch einfach mal bei
![[]](/images/popup.gif) Wikipedia (klick!): Chinesischer Restsatz
Obige Kongruenz ist aber nach einem Satz (Chinesischer Restsatz, 1. Version,
siehe Satz 4.11 in "Elementare und algebraische Zahlentheorie" von Müller-
Stach/Piontkowski) nicht lösbar:
Denn schon bei
$x [mm] \equiv \blue{1} \mod \red{\,3}$ [/mm] und $x [mm] \equiv \blue{3} \mod \red{\,9}$
[/mm]
ist offenbar
[mm] $d:=\ggT(\red{\,3\,},\red{\,9\,})=3\,,$
[/mm]
und damit gilt
$d [mm] \nmid (\blue{1}-\blue{3})$
[/mm]
wegen $3 [mm] \nmid (-2)\,,$ [/mm] also
[mm] $\blue{1} \not\equiv \blue{3} \mod \underbrace{3}_{=d}\,.$
[/mm]
Das ist übrigens auch so schon relativ logisch, dass diese simultanen Kongruenzen
nicht lösbar sind, denn:
$x [mm] \equiv [/mm] 3 [mm] \mod [/mm] 9$
bedeutet, dass bei einer Division von x durch 9 der Rest 3 bleibt. Damit ist
die Zahl x darstellbar als
[mm] $x=k*9+3\,$ [/mm] (mit einem $k [mm] \in \IZ$),
[/mm]
womit sie auch schon durch 3 teilbar sein muss. Damit kann sie $x [mm] \equiv [/mm] 1 [mm] \mod [/mm] 3$ nicht
mehr erfüllen!
Gruß,
Marcel
|
|
|
|
