Linearkombination Chin. Rests. < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:32 Mo 06.01.2014 | | Autor: | sqe |
Hallo,
ich möchte mithilfe des chinesischen Restesatzes die Linearkombination von gcd(5,1) bestimmen. Wie der chinesische Restesatz an sich funktioniert ist mir klar, allerdings habe ich ihn noch nie mit gcd(x, 1) ausgeführt.
Zuvor habe ich die Linearkombination für gcd(3,2) bestimmt, da erhalte ich: 1=1*3+(-1)*2. Wenn ich das gleiche nun für gcd(5,1) mache, würde ich spontan schreiben: 5=5*1+0 => 1=5-5*1. Laut der Lösung soll man aber 1=1*1+0*5 erhalten und ich komme nicht darauf. Wie ist hier die Vorgehensweise?
Vielen Dank.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> gcd(5,1)
> Hallo,
> ich möchte mithilfe des chinesischen Restesatzes die
> Linearkombination von gcd(5,1) bestimmen. Wie der
> chinesische Restesatz an sich funktioniert ist mir klar,
> allerdings habe ich ihn noch nie mit gcd(x, 1)
> ausgeführt.
> Zuvor habe ich die Linearkombination für gcd(3,2)
> bestimmt, da erhalte ich: 1=1*3+(-1)*2. Wenn ich das
> gleiche nun für gcd(5,1) mache, würde ich spontan
> schreiben: 5=5*1+0 => 1=5-5*1.
Seit wann ist 1=5-5*1?
Laut der Lösung soll man
> aber 1=1*1+0*5 erhalten und ich komme nicht darauf. Wie ist
> hier die Vorgehensweise?
>
> Vielen Dank.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:23 Mo 06.01.2014 | | Autor: | sqe |
> Seit wann ist 1=5-5*1?
Darum geht es mir ja. Wenn ich das gleiche Vorgehen wie bei der zuvor gerechneten Aufgabe anwende, gelange ich zu diesem falschen Ergebnis. Wie kommt man denn auf die angegebene Lösung?
|
|
|
| |
|
Hallo sqe,
> > Seit wann ist 1=5-5*1?
>
> Darum geht es mir ja. Wenn ich das gleiche Vorgehen wie bei
> der zuvor gerechneten Aufgabe anwende, gelange ich zu
> diesem falschen Ergebnis. Wie kommt man denn auf die
> angegebene Lösung?
Ich kann nicht nachvollziehen, wie Du zu diesem Ergebnis kommst. Vielleicht machst Du mal vor, wie Du hier das (recht mechanische) Schema des erweiterten euklidischen Algorithmus benutzt, um zu dieser Lösung zu gelangen.
Hier ist der Weg ja ausnehmend kurz, das ist also nicht viel Arbeit.
Irgendwo darin muss der Fehler liegen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:33 Mo 06.01.2014 | | Autor: | sqe |
Hallo reverend,
der Rechenweg ist in der Tat sehr kurz; ich möchte diesen zuvor noch an einem anderen Beispiel demonstrieren, um zu prüfen, ob ich überhaupt richtig vorgehe.
Sei gcd(90,37) gesucht.
90 = 2 * 37 + 16
37 = 2 * 16 + 5
16 = 3 * 5 + 1
1 = 16 - 3 * 5
1 = 16 - 3 * (37 - 2 * 16)
= -3 * 37 + 7 * 16
1 = -3 * 37 + 7 * (90 - 2 * 37)
= 7 * 90 - 17 * 37
Die Linearkombination lautet also:
1 = 7 * 90 + (-17) * 37
Wenn ich das für 5 und 1 durchrechne, komme ich nur bis hier:
5 = 5 * 1 + 0
???
Vielleicht stehe ich auch einfach nur total auf dem Schlauch. Die ... + 0 sagt mMn doch auch nur aus, dass die beiden Zahlen nicht teilerfremd zueinander sind. Wie ich daraus dann aber mögliche Linearkombinationen ermitteln sind, wird mir irgendwie nicht klar.
Viele Grüße
|
|
|
| |
|
> Hallo reverend,
>
> der Rechenweg ist in der Tat sehr kurz; ich möchte diesen
> zuvor noch an einem anderen Beispiel demonstrieren, um zu
> prüfen, ob ich überhaupt richtig vorgehe.
>
> Sei gcd(90,37) gesucht.
> 90 = 2 * 37 + 16
> 37 = 2 * 16 + 5
> 16 = 3 * 5 + [mm] \red{1}
[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
Jetzt noch den nächsten Schritt:
5 = [mm] 5*\red{1} [/mm] + 0
Mit diesem Verfahren findet man eigentlich den ggT zweier Zahlen. Dabei ist der ggT der letzte Rest in der Kette, bevor der Rest 0 auftaucht. In obigem Beispiel ist er 1. Deshalb funktioniert der Chin. Restwertsatz, bei dem die 1 als Linearkombination zweier Zahlen gesucht ist, auch nur, wenn der ggT = 1 ist.
>
> 1 = 16 - 3 * 5
> 1 = 16 - 3 * (37 - 2 * 16)
> = -3 * 37 + 7 * 16
> 1 = -3 * 37 + 7 * (90 - 2 * 37)
> = 7 * 90 - 17 * 37
>
> Die Linearkombination lautet also:
> 1 = 7 * 90 + (-17) * 37
>
> Wenn ich das für 5 und 1 durchrechne, komme ich nur bis
> hier:
>
> 5 = 5 * 1 + 0
> ???
>
Genau: Mit den beiden Zahlen x und 1 erhältst du sofort im nächsten Schritt den Rest 0. Das bedeutet aber, dass du denvorhergehenden "Rest" nehmen müsstest, der aber gar nicht existiert. Wenn du jetzt noch mal oben auf meine Ergänzungszeile schaust, siehtst du aber, dass gerade die rote 1 in meiner Darstellung der Rest aus deiner letzten Zeile davor ist ist, nämlich die rote 1 darüber.
Mit anderen Worten: gcd(x,1)=1.
Das sollte dich nicht verwirren. Wenn du [mm] \vektor{3 \\ 5} [/mm] als Linearkombination der Vektoren [mm] \vektor{3 \\ 5} [/mm] und [mm] \vektor{2 \\ 7} [/mm] schreiben sollst, fängst du hoffentlich auch nicht an, ein Lineares Gleichungssystem zu lösen, sondern schreibst einfach [mm] \vektor{3 \\ 5} [/mm] = [mm] 1*\vektor{3 \\ 5} [/mm] + [mm] 0*\vektor{2 \\ 7} [/mm] hin.
Genau so schreibst du gcd(x,1)=1*1 + 0*x. Das ist ein trivialer Sonderfall.
> Vielleicht stehe ich auch einfach nur total auf dem
> Schlauch. Die ... + 0 sagt mMn doch auch nur aus, dass die
> beiden Zahlen nicht teilerfremd zueinander sind.
Nein, im "normalen" Verfahren eben, wie bereits geschildert,
Der "Pseudo-Rest" vorher.
Ich schreibe dir mal auf, wie man in einem Computerprogramm den ggT programmiert:
ggT(a,b)
Befehl 1: c = Rest von a:b
Befehl 2: Falls c=0 ist, gehe zu Befehl 6
Befehl 3: Ersetze a durch b
Befehl 4: Ersetze b durch c
Befehl 5: Springe zu Befehl 1 zurück
Befehl 6: Gib b als ggT(a,b) aus.
Du erhältst nun der Reihe nach für die folgenden Beispiele für die Werte immer an der Stelle "Befehl 1":
a b c
ggT(36,54): 36 54 36
54 36 18
36 18 0
Ausgabe 18
a b c
ggT(54,36): 54 36 18
36 18 0
Ausgabe 18
a b c
ggT(5,1): 5 1 0
Ausgabe 1
a b c
ggT(1,5): 1 5 1
5 1 0
Ausgabe 1
Wenn man Eingaben mit 0 zulässt, erhält man allerdings
a b c
ggT(0,5): 0 5 0
Ausgabe 0 - unsinniger Weise
aber
a b c
ggT(5,0): 5 0 Absturz wegen Division durch 0
>
Wie ich daraus dann aber mögliche Linearkombinationen ermitteln
> sind, wird mir irgendwie nicht klar.
>
> Viele Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:36 So 12.01.2014 | | Autor: | sqe |
Hallo HJKweseleit,
herzlichen Dank für Deine tolle Erklärungen - sie haben mir sehr weitergeholfen und ich bin einen großen Schritt weitergekommen!
Alles Gute für Dich und viele Grüße
|
|
|
|
