erw. Euklid via Linearkombi.? < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:18 So 11.01.2009 | | Autor: | kawu |
Hallo.
Ich habe gestern schon einmal wegen dem erweitereten Euklid gefragt und habe es auch verstanden.
Gerade habe ich mir noch einmal http://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus angesehen und interessiere mich nun für die zweite Variante des dort gezeigten Beispiels. Ich würde gerne lernen, wie die s und t von ggT(a,b) = s*a+t*b schon _während_ dem euklidischen Algorithmus ausgerechnet werden mit der dort vorgestellten Linearkombination. Nur leider verstehe ich bis jetzt nicht, was für eine Logik sich dahinter versteckt.
Würde mir da jemand helfen? :)
lg, KaWu
|
|
| |
|
Hallo kawu,
> Hallo.
>
> Ich habe gestern schon einmal wegen dem erweitereten Euklid
> gefragt und habe es auch verstanden.
>
> Gerade habe ich mir noch einmal
> http://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus
> angesehen und interessiere mich nun für die zweite Variante
> des dort gezeigten Beispiels. Ich würde gerne lernen, wie
> die s und t von ggT(a,b) = s*a+t*b schon _während_ dem
> euklidischen Algorithmus ausgerechnet werden mit der dort
> vorgestellten Linearkombination. Nur leider verstehe ich
> bis jetzt nicht, was für eine Logik sich dahinter
> versteckt.
>
> Würde mir da jemand helfen? :)
>
[mm]\blue{99}=1*\blue{78}+\blue{21} \gdw \blue{21}=1*\blue{99}-1*\blue{78} \ \left(1\right)[/mm]
[mm]\blue{78}=3*\blue{21}+\blue{15} \gdw \blue{15}=1*\blue{78}-3*\blue{21}[/mm]
Nun wird 21 ersetzt durch (1):
[mm]\blue{15}=1*\blue{78}-3*\blue{21}=1*\blue{78}-3*\left(1*\blue{99}-1*\blue{78}\right)=-3*\blue{99}+4*\blue{78} \ \left(2\right)[/mm]
Weiter:
[mm]\blue{21}=1*\blue{15}+\blue{6} \gdw \blue{6}=1*\blue{21}-1*\blue{15}[/mm]
Nun werden 21 durch (1) und 15 durch (2) ersetzt:
[mm]\blue{6}=1*\blue{21}-1*\blue{15}=1*\left(1*\blue{99}-1*\blue{78} \right)-1*\left(-3*\blue{99}+4*\blue{78} \right)=4*\blue{99}-5*\blue{78} \ \left(3\right)[/mm]
Nächster Schritt:
[mm]\blue{15}=2*\blue{6}+\blue{6} \gdw \blue{3}=1*\blue{15}-2*\blue{6}[/mm]
Nun werden 15 durch (2) und 6 durch (3) ersetzt:
[mm]\blue{3}=1*\blue{15}-2*\blue{6}=1*\left(-3*\blue{99}+4*\blue{78} \right)-2*\left(4*\blue{99}-5*\blue{78} \right)=-11*\blue{99}+14*\blue{78} \ \left(4\right)[/mm]
>
> lg, KaWu8
>
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:02 Mo 12.01.2009 | | Autor: | kawu |
Mh, ich habe es wohl ein wenig missverständlich asgedrückt. eigentlich meite ich das zweite Beispiel, das mit den Pfeilen. Daran bin ich interessiert, weil es nach geringerem Aufwand aussieht. Kann mir das jemand mit ausreichend Geduld erklären? :)
lg, KaWu
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:17 Mo 12.01.2009 | | Autor: | reverend |
Hallo kawu,
das Problem ist nicht die Geduld, sondern dass es ziemlich lange dauert, verständliche und womöglich farbig markierte Beiträge (wie den von MathePower) zu verfassen.
Was genau verstehst Du nicht an dem wiki-Beispiel?
lg,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:57 Mo 12.01.2009 | | Autor: | kawu |
Das ist mir klar und ich will auf keinen Fall den Eindruck erwecken, als würde ich das nicht zu würdigen wissen.
Mein Problem an dem Beispiel ist wie folgt:
[mm] $\begin{array}{rclcrclcl} \underline{99}&=&1\cdot \underline{78}+\underline{21}&\iff& \underline{21}&=&&&1\cdot\underline{99}-1\cdot \underline{78}\\ \underline{78}&=&3\cdot \underline{21}+\underline{15}&\iff& \underline{15}&=&1\cdot\underline{78}-3\cdot \underline{21}&=&-3\cdot\underline{99}+4\cdot \underline{78}\\ \underline{21}&=&1\cdot \underline{15}+\underline{\ 6}&\iff& \underline{\ 6}&=&1\cdot\underline{21}-1\cdot\underline{15}&=&4\cdot\underline{99}-5\cdot \underline{78}\\ \underline{15}&=&2\cdot \underline{\ 6}+\underline{\ 3}&\iff& \underline{\ 3}&=&1\cdot\underline{15}-2\cdot \underline{\ 6}&=&-11\cdot\underline{99}+14\cdot \underline{78} \end{array}$
[/mm]
Die erste Zeile leuchtet mir noch ein. Die ist wie beim gewöhnlichen eA.
Die Zweite Zeile verwirrt mich: Wie komme ich auf -3*99+4*78.
Wie muss ich 15=1*21-1*15 umformen, um das zu erhalten??
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:00 Mo 12.01.2009 | | Autor: | MathePower |
Hallo kawu,
> Das ist mir klar und ich will auf keinen Fall den Eindruck
> erwecken, als würde ich das nicht zu würdigen wissen.
>
> Mein Problem an dem Beispiel ist wie folgt:
>
> [mm]\begin{array}{rclcrclcl} \underline{99}&=&1\cdot \underline{78}+\underline{21}&\iff& \underline{21}&=&&&1\cdot\underline{99}-1\cdot \underline{78}\\ \underline{78}&=&3\cdot \underline{21}+\underline{15}&\iff& \underline{15}&=&1\cdot\underline{78}-3\cdot \underline{21}&=&-3\cdot\underline{99}+4\cdot \underline{78}\\ \underline{21}&=&1\cdot \underline{15}+\underline{\ 6}&\iff& \underline{\ 6}&=&1\cdot\underline{21}-1\cdot\underline{15}&=&4\cdot\underline{99}-5\cdot \underline{78}\\ \underline{15}&=&2\cdot \underline{\ 6}+\underline{\ 3}&\iff& \underline{\ 3}&=&1\cdot\underline{15}-2\cdot \underline{\ 6}&=&-11\cdot\underline{99}+14\cdot \underline{78} \end{array}[/mm]
>
> Die erste Zeile leuchtet mir noch ein. Die ist wie beim
> gewöhnlichen eA.
>
> Die Zweite Zeile verwirrt mich: Wie komme ich auf
> -3*99+4*78.
>
> Wie muss ich 15=1*21-1*15 umformen, um das zu erhalten??
>
Ich habe Dir das in diesem Post erläutert.
Gruß
MathePower
|
|
|
| |
|
Hallo kawu,
> Das ist mir klar und ich will auf keinen Fall den Eindruck
> erwecken, als würde ich das nicht zu würdigen wissen.
>
> Mein Problem an dem Beispiel ist wie folgt:
>
> [mm]\begin{array}{rclcrclcl} \underline{99}&=&1\cdot \underline{78}+\underline{21}&\iff& \underline{21}&=&&&1\cdot\underline{99}-1\cdot \underline{78}\\ \underline{78}&=&3\cdot \underline{21}+\underline{15}&\iff& \underline{15}&=&1\cdot\underline{78}-3\cdot \underline{21}&=&-3\cdot\underline{99}+4\cdot \underline{78}\\ \underline{21}&=&1\cdot \underline{15}+\underline{\ 6}&\iff& \underline{\ 6}&=&1\cdot\underline{21}-1\cdot\underline{15}&=&4\cdot\underline{99}-5\cdot \underline{78}\\ \underline{15}&=&2\cdot \underline{\ 6}+\underline{\ 3}&\iff& \underline{\ 3}&=&1\cdot\underline{15}-2\cdot \underline{\ 6}&=&-11\cdot\underline{99}+14\cdot \underline{78} \end{array}[/mm]
>
> Die erste Zeile leuchtet mir noch ein. Die ist wie beim
> gewöhnlichen eA.
>
> Die Zweite Zeile verwirrt mich: Wie komme ich auf
> -3*99+4*78.
Davor steht ja [mm] $15=1\cdot{}78-3\cdot{}\red{21}$, [/mm] wie das zustande kommt, ist klar, oder? Steht ja da 
Darüber steht genau, was [mm] $\red{21}$ [/mm] ist, nämlich [mm] $\red{21=1\cdot{}99-1\cdot{}78}$
[/mm]
Das wird eingesetzt: [mm] $15=1\cdot{}78-3\cdot{}\red{21}=1\cdot{}78-3\cdot{}\left(\red{1\cdot{}99-1\cdot{}78}\right)$
[/mm]
ausrechnen: [mm] $=1\cdot{}78-3\cdot{}99+3\cdot{}78=-3\cdot{}99+4\cdot{}78$
[/mm]
>
> Wie muss ich 15=1*21-1*15 ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Wo hast du das her?
> umformen, um das zu erhalten??
>
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:27 Di 13.01.2009 | | Autor: | kawu |
Das ist ja das gleiche was ich bisher gemacht habe, nur Rückwärts. Sorry, das war eine dumme Frage. Habe das beim ersten Post nicht gesehen.
|
|
|
|
