Chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo Leute,
ich habe eine Frage zu einem Beispiel zum C.R.
[mm] x\equiv [/mm] 2 mod 3
[mm] x\equiv [/mm] 3 mod 5
[mm] x\equiv [/mm] 2 mod 7
1) Die [mm] m_i [/mm] sind alle paarweise teilerfremd
2) M=3*5*7=105
3) [mm] N_1=35, N_2=21, N_3=15
[/mm]
4)
[mm] r_1 [/mm] 35 [mm] \equiv [/mm] 2 (mod 3) => [mm] r_1 [/mm] = 1
[mm] r_2 [/mm] 21 [mm] \equiv [/mm] 3 (mod 5) => [mm] r_2 [/mm] = 3
[mm] r_3 [/mm] 15 [mm] \equiv [/mm] 2 (mod 7) => [mm] r_3 [/mm] = 2
5)
x [mm] \equiv N_1*r_1 [/mm] + [mm] N_2*r_2 [/mm] + [mm] N_3*r_3 [/mm] (mod M)
x [mm] \equiv [/mm] 128 (mod 105)
x=23
So, hier steckt meine Frage, die geben dann als Lösung nicht x=128 an, sondern x=23. Aber wie kommen die hier auf x=23?? und wäre als Ergebnis x=128 auch richtig??
Eine andere Frage von mir betrifft den Schritt 4). Hier wurden die [mm] r_i [/mm] ja eher durch raten herausgefunden? Wie könnte man das auch rechnerisch herausbekommen???
Danke schon mal für eure Hilfe.
Grüße
|
|
| |
|
> Hallo Leute,
>
> ich habe eine Frage zu einem Beispiel zum C.R.
>
> [mm]x\equiv[/mm] 2 mod 3
> [mm]x\equiv[/mm] 3 mod 5
> [mm]x\equiv[/mm] 2 mod 7
>
> 1) Die [mm]m_i[/mm] sind alle paarweise teilerfremd ![[ok]](/images/smileys/ok.gif "[ok]")
>
> 2) M=3*5*7=105
>
> 3) [mm]N_1=35, N_2=21, N_3=15[/mm]
>
> 4)
>
> [mm]r_1[/mm] 35 [mm]\equiv[/mm] 2 (mod 3) => [mm]r_1[/mm] = 1
>
> [mm]r_2[/mm] 21 [mm]\equiv[/mm] 3 (mod 5) => [mm]r_2[/mm] = 3
>
> [mm]r_3[/mm] 15 [mm]\equiv[/mm] 2 (mod 7) => [mm]r_3[/mm] = 2
>
> 5)
>
> x [mm]\equiv N_1*r_1[/mm] + [mm]N_2*r_2[/mm] + [mm]N_3*r_3[/mm] (mod M)
>
> x [mm]\equiv[/mm] 128 (mod 105)
>
> x=23
>
> So, hier steckt meine Frage, die geben dann als Lösung
> nicht x=128 an, sondern x=23. Aber wie kommen die hier auf
> x=23??
Da 128>105, wird 105 subtrahiert. Modulo 105 können
ja alle Zahlen auf einen Wert in [mm] $\{\,0, 1, 2,\,.....\,104\,\}$
[/mm]
reduziert werden, und spätestens für das Ergebnis
sollte man dies auch tun.
> und wäre als Ergebnis x=128 auch richtig??
etwa so richtig wie die Angabe [mm] \alpha [/mm] = 390° für einen
Dreieckswinkel ...
> Eine andere Frage von mir betrifft den Schritt 4). Hier
> wurden die [mm]r_i[/mm] ja eher durch raten herausgefunden? Wie
> könnte man das auch rechnerisch herausbekommen???
Da hilft der ![[]](/images/popup.gif) erweiterte euklidische Algorithmus .
> Danke schon mal für eure Hilfe.
>
> Grüße
LG Al-Chw.
|
|
|
| |
|
HI Al-Chwarizmi,
danke für deine Antwort.
Hatte mir schon gedacht, dass man das mit dem E.A. macht. Nur haben wir es ja hier jetzt mit 3 Zahlen zu tun, und nicht um 2.
Also ggt(3,5,7). Der erweiterte E.A. ist ja das Rückwärtsrechnen vom E.A. Wie kann man das aber jetzt auf 3 Zahlen übertragen??
Also erstmal
ggt(3,5)=1, denn
5=1*3+2
3=1*2+1
2=2*1*0
und dann
ggT(1,7)=1, denn
7=7*1+0,
so, wie bekomme ich jetzt hier durch Rückwärtsrechnen die Zahlen [mm] r_1=1, r_2=3 [/mm] und r_=2 heraus??
Kannst du mir das vielleicht erklären?
Und zu dem Ergebis x=128. Ok, x=23 ist die kleine Variante. Aber x=128 müsste sonst trotzdem richtig sein, denn wenn man die Probe macht, geht bei der Aufgabe alles auf....
Grüße
|
|
|
| |
|
> HI Al-Chwarizmi,
>
> danke für deine Antwort.
>
> Hatte mir schon gedacht, dass man das mit dem E.A. macht.
> Nur haben wir es ja hier jetzt mit 3 Zahlen zu tun, und
> nicht um 2.
>
> Also ggt(3,5,7). Der erweiterte E.A. ist ja das
> Rückwärtsrechnen vom E.A. Wie kann man das aber jetzt auf
> 3 Zahlen übertragen??
>
> Also erstmal
>
> ggt(3,5)=1, denn
>
> 5=1*3+2
> 3=1*2+1
> 2=2*1*0
>
> und dann
>
> ggT(1,7)=1, denn
>
> 7=7*1+0,
>
> so, wie bekomme ich jetzt hier durch Rückwärtsrechnen die
> Zahlen [mm]r_1=1, r_2=3[/mm] und r_=2 heraus??
>
> Kannst du mir das vielleicht erklären?
Nach den Vorarbeiten mit den [mm] N_i [/mm] geht dies anders und
einfacher. Siehe unten !
> Und zu dem Ergebis x=128. Ok, x=23 ist die kleine Variante.
> Aber x=128 müsste sonst trotzdem richtig sein, denn wenn
> man die Probe macht, geht bei der Aufgabe alles auf....
Natürlich stimmt dies auch, aber es ist doch natürlich,
dass man den kleinstmöglichen nichtnegativen Rest angibt !
Sonst kannst du auch das Ergebnis 2753 angeben und
dem geneigten und lieben Korrektor die Arbeit überlassen,
zu prüfen, ob dies modulo 105 auch noch stimmt.
Wir hatten:
1) Die $ [mm] m_i [/mm] $ sind alle paarweise teilerfremd
2) M=3*5*7=105
3) $ [mm] N_1=35, N_2=21, N_3=15 [/mm] $
4)
a) $ [mm] r_1 [/mm] *35 [mm] \equiv [/mm] $ 2 (mod 3) => $ [mm] r_1 [/mm] $ = 1
b) $ [mm] r_2 [/mm] *21 [mm] \equiv [/mm] $ 3 (mod 5) => $ [mm] r_2 [/mm] $ = 3
c) $ [mm] r_3 [/mm] *15 [mm] \equiv [/mm] $ 2 (mod 7) => $ [mm] r_3 [/mm] $ = 2
5)
x $ [mm] \equiv N_1\cdot{}r_1 [/mm] $ + $ [mm] N_2\cdot{}r_2 [/mm] $ + $ [mm] N_3\cdot{}r_3 [/mm] $ (mod M)
x $ [mm] \equiv [/mm] $ 128 (mod 105)
x=23
Die Berechnungen der Werte [mm] r_i [/mm] nach 4)a) , 4)b) und 4)c)
kann man jede einzeln durchführen.
Bevor man (allenfalls) den Restsatz bemüht, gibt es aber
Möglichkeiten der systematischen (!) Vereinfachung.
Nehmen wir mal das Beispiel 4)b):
4)a) $\ [mm] r_1 [/mm] *35 [mm] \equiv [/mm] 2\ \ (mod\ 3)$
Modulo 3 kann man den Faktor 35 zerlegen in 35=11*3+2
und kommt damit zur neuen Äquivalenz:
$\ [mm] r_1 [/mm] *2 [mm] \equiv [/mm] 2\ \ (mod\ 3)$
Division durch 2 (teilerfremd zu 3 !) liefert
$\ [mm] r_1 \equiv [/mm] 1\ \ (mod\ 3)$
also [mm] r_1=1 [/mm] (Rest im Grundbereich [mm] $\{\,0,1,2\,\}$ [/mm] modulo 3)
LG Al-Chw.
|
|
|
| |
|
Hi nochmal,
also ok. in diesem beispiel habe ich das verstanden. aber schau dir mal diese zahlen bitte an:
[mm] 240*r_1 \equiv [/mm] 3 mod 17
Hier ist [mm] r_1=10, [/mm] aber wie würdest du das mit deiner Variante dort oben herausbekommen??
Hier ist es ja nicht einfach, ein Vielfaches von 17 + 3 zu finden, das durch 240 teilbar ist....
|
|
|
| |
|
> Hi nochmal,
>
> also ok. in diesem beispiel habe ich das verstanden. aber
> schau dir mal diese zahlen bitte an:
>
> [mm]240*r_1 \equiv[/mm] 3 mod 17
>
> Hier ist [mm]r_1=10,[/mm] aber wie würdest du das mit deiner
> Variante dort oben herausbekommen??
>
> Hier ist es ja nicht einfach, ein Vielfaches von 17 + 3 zu
> finden, das durch 240 teilbar ist....
Hallo Steve,
da wir es doch immer noch mit recht kleinen, handlichen
Zahlen zu tun haben, würde ich auch dies ohne Restsatz
versuchen:
1.) da 240=14*17+2 ist, kann man die Äquivalenz zu
$\ [mm] 2*r_1 \equiv\ [/mm] 3\ \ (mod\ 17)$
vereinfachen.
2.) Nun betrachte ich zunächst die Gleichung
$\ 2*x [mm] \equiv\ [/mm] 1\ \ (mod\ 17)$
Sie hat die (leicht zu findende) Lösung x=9
3.) Da wir in der obigen Gleichung rechts nicht eine 1,
sondern eine 3 hatten, multiplizieren wir die
Gleichung
$\ 2*9 [mm] \equiv\ [/mm] 1\ \ (mod\ 17)$
noch mit dem Faktor 3 und haben
$\ 2*27 [mm] \equiv\ [/mm] 3\ \ (mod\ 17)$
Damit haben wir eine Lösung (nämlich [mm] r_1=27)
[/mm]
für die ursprüngliche Gleichung.
4.) Modulo 17 wird die Lösung 27 noch zu [mm] r_1=10
[/mm]
reduziert.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:30 Mi 25.05.2011 | | Autor: | steve.joke |
ok,
danke dir.
grüße
|
|
|
|
