Umkehrung Euklidischer Algorithmus

25.10.2011, 11:54

Hachiko

Umkehrung Euklidischer Algorithmus

Hallo Liebe Forumnutzer,

Wie man mittels Euklidischen Algorithmus den ggT findet ist mir klar

Die Frage die mich quält ist wie man den Algorithmus rückwirkend einsetzt sodass man folgendes z.B lösen kann:

451x + 176y = 11

x und y sind gefragt

Es gibt ein gelöstes Beispiel im Buch. Der geht so:

zuerst ggT (59,11)

59 = 11*5+4
11 = 4*2+3
4 = 3*1+1
3 = 1*3+0

soweit verstehe ich es ganz gut!

nun kommt die umkehrung!!

1 = 4 - 3*1
= 4 - (11 - 4 * 2) * 1 ---> das verstehe ich schon noch!
= 3 * 4 - 1*11 ---> hääää wieso das? woher diese zahlen??
= 3 * (59 - 5 * 11) - 1 * 11 ----> kommt von der mysteriösen zeile oberhalb!
= 3 * 59 - 16 * 11 ----> dahinter sehe ich einfach keine logik mehr!!

danach kommt nichts mehr!

Bisher weiss ich, dass bei 451x + 176y = 11

11 der ggT ist aber wie ich rückwirkend mittels euklidischen Algorithmus wie oben gezeigt einsetze weiss ich leider nicht =(

Bitte dringend um euer Rat

Vielen Dank

25.10.2011, 12:02

Helferlein

Auf diesen Beitrag antworten »

1 = 4 - 3*1 --> Umformung von 4=3*1+1
= 4 - (11 - 4 * 2) * 1 ---> 3=11-4*2 (Umformung des zweiten Schritts von oben) eingesetzt
= 3 * 4 - 1*11 ---> Ausmultipliziert und zusammengefassen
= 3 * (59 - 5 * 11) - 1 * 11 ----> 4=59-11*5 (Umformung des ersten Schritts von oben) eingesetzt
= 3 * 59 - 16 * 11 ----> Ausmultipliziert und zusammengefasst.

25.10.2011, 12:57

Hachiko

Auf diesen Beitrag antworten »

Vielen Dank für die Antwort aber leider ist mir das immer noch unklar

1 = 4 - 3*1 --> Umformung von 4=3*1+1
= 4 - (11 - 4 * 2) * 1 ---> 3=11-4*2 (Umformung des zweiten Schritts von oben) eingesetzt

Also die Umformung des zweiten Schritts verstehe ich.

= 3 * 4 - 1*11 ---> Ausmultipliziert und zusammengefassen

Aber wenn ich 4 - (11 - 4 * 2) * 1 ausmultipliziere dann komme ich ja auf 4 - (3) * 1 sprich 1.

Mir ist immer noch nicht klar wie man hier auf 3 * 4 - 1*11 kommt!

Bitte entschuldigt meine Unwissenheit unglücklich

25.10.2011, 16:39

Helferlein

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 4 - (11 - 4 \cdot 2) \cdot 1 = 4 - 11\cdot 1+4\cdot 2\cdot 1<br /> =4\cdot(1+2\cdot 1)-11\cdot 1 = 4\cdot3-11\cdot 1 \end{eqnarray*}$

Das Ziel ist ja, sich eine Zeile rückwärts zu bewegen, also den ggt durch 4 und 11 darzustellen.

25.10.2011, 18:37

Hachiko

Auf diesen Beitrag antworten »

Danke nochmals für die Antwort

Kann man ein minus einfach so in einem mal umwandeln?

Aus 4 - 11 * 1 + 4 * 2 * 1 machst du 4 * (1 + 2 * 1) - 11 * 1

Außerdem gibt es im ersten Term 2 einser. Im zweiten aber aufeinmal 3 einser!

Ich habe es dennoch ausprobiert und komme so weit:

$\begin{eqnarray*} 451x + 176y = 11 \end{eqnarray*}$

$\begin{eqnarray*} 11 = 77 - 22 \cdot 3 \end{eqnarray*}$

$\begin{eqnarray*} = 77 - (99-77\cdot 1)\cdot 3 \end{eqnarray*}$
$\begin{eqnarray*} = 77 - 99\cdot 3 + 77\cdot 1 \cdot 3 \end{eqnarray*}$

Wegen dem Minus wird aus dem minus ein plus in der klammer. Aber die Rechnung würde nur stimmen wenn es bei einem minus bliebe. Dann würde es 11 rauskommen..

Selbst wenn ich jetzt weiter mache und so vorgehe wie vorhin beschrieben dann müsste jetzt da stehen:

$\begin{eqnarray*} =77\cdot (3+3\cdot 1)-99\cdot 1 \end{eqnarray*}$

das ist aber ebenfalls nicht 11! da komme ich leider einfach nicht mehr weiter unglücklich

(wobei wie oben erwähnt woher die zusätzliche eins? kann man sie einfach dazu schreiben weil mal eins genommen kein unterschied macht? ist das der grund?)

Vielen Dank und nochmal entschuldigung für meine dummheit!

25.10.2011, 20:16

Helferlein

Auf diesen Beitrag antworten »

OK, da anscheinend auch einige Unsicherheiten in den einfachen Rechengesetzten (z.B. -x = -1*x) zu bestehen scheint,
gehe ich etwas ausführlicher vor:

Der Euklidische Algorithmus liefert die Schritte

$\begin{eqnarray*} 59 = 11\cdot5+4 \Leftrightarrow 59-11\cdot 5=4 \end{eqnarray*}$

$\begin{eqnarray*} 11 = 4\cdot2+3 \Leftrightarrow 11-4\cdot2=3 \end{eqnarray*}$

$\begin{eqnarray*} 4 = 3\cdot1+1 \Leftrightarrow 4-3\cdot 1 =1 \end{eqnarray*}$

Zum Umkehren starten wir in der letzten Zeile:
$\begin{eqnarray*} 1=4-3\cdot 1 \end{eqnarray*}$

Nutzen dann die zweite Zeile
$\begin{eqnarray*} 1=4-(11-4\cdot 2) \cdot 1=4-11+4\cdot2 = 4+4\cdot2-11=4\cdot3-11 \end{eqnarray*}$

Und schließlich die erste Zeile
$\begin{eqnarray*} 1=(59-11\cdot5)\cdot3-11=59\cdot3-11\cdot15-11=59\cdot3-11\cdot16 \end{eqnarray*}$

25.10.2011, 22:37

Hachiko

Auf diesen Beitrag antworten »

Zitat:

OK, da anscheinend auch einige Unsicherheiten in den einfachen Rechengesetzten (z.B. -x = -1*x) zu bestehen scheint...

Es gibt auf diesen Planeten keine größere Niete in Mathematik als meine Wenigkeit!!!

so viel dazu..

Aber nach ewigem herumprobieren habe ich folgendes erreicht:

Angabe: $\begin{eqnarray*} 451x + 176y = 11 \end{eqnarray*}$

mittels Euklidischem algorithmus müssen x und y gefunden werden.

$\begin{eqnarray*} ggT(451,176) = 11 \end{eqnarray*}$

$\begin{eqnarray*} 11=77-22\cdot 3 \end{eqnarray*}$
$\begin{eqnarray*} = 77 - (99-77\cdot 1)\cdot3) \end{eqnarray*}$
$\begin{eqnarray*} = 77\cdot 4 - 99 \cdot 3 \end{eqnarray*}$
$\begin{eqnarray*} = (176 - 99\cdot 1) \cdot 4 - 99\cdot 3 \end{eqnarray*}$
$\begin{eqnarray*} = 176 \cdot 4 - 99 \cdot 7 \end{eqnarray*}$
$\begin{eqnarray*} = 176 \cdot 4 - (451 - 176 \cdot 2) \cdot 7 \end{eqnarray*}$
$\begin{eqnarray*} = 176 \cdot 18 - 451 \cdot 7 \end{eqnarray*}$

leider habe ich keine kürzere Möglichkeit gefunden und musste 3 mal umformen! Gibt es eine kleinere Version dessen sodass ich eher zum 451x komme?

Da am Ende ein Minus vor 451 steht habe ich -7 als x genommen. Mit +7 funktioniert es nicht. Es geht nur wenn ich -7 für x und +18 für y einsetze.

Ist es nur ein glücklicher Zufall dass ich hier bei meiner Berechnung nur das Vorzeichen umdrehen brauche oder ist meine Überlegung tatsächlich richtig?

Jedenfalls großen Dank an Helferlein Freude

Bin froh, dass ich überhaupt irgendwas glaubwürdiges vorzuweisen habe...

Ich würde mich dennoch freuen wenn mir meine Überlegung als richtig oder falsch bestätigt werden würde.

Vielen Herzlichen Dank

25.10.2011, 23:00

Helferlein

Auf diesen Beitrag antworten »

Du solltest 451x+176y=11 lösen und hast herausbekommen, dass $\begin{eqnarray*} 11=176\cdot 18-451\cdot 7=176\cdot18+(-7)\cdot451 \end{eqnarray*}$ .

Wenn Du das vergleichst, siehst Du, dass y=18 und x=-7 völlig richtig ist.

Neue Frage »

Antworten »

Umkehrung Euklidischer Algorithmus

Verwandte Themen