erweiterter euklidischer algorithmus

Neue Frage »

starcraft42 Auf diesen Beitrag antworten »
erweiterter euklidischer algorithmus
hallo, ich hab grad ein kleines Problem beim rechnen mit dem erweiterter euklidischer algorithmus.

am Bsp von Wikipedia ggT(99,78)

Zeile I
Zeile II
Zeile III
Zeile IV
Zeile V

<-- hier wird die 3 der Zeile V durch Zeile IV ersetzt
<-- hier wird 6 der Zeile IV durch III ersetzt
hier verstehe ich zwar das die 15 ersetzt wurde aber woher kommt plötzlich 3 * (78.... ? und -2 * 21 her?
hier verstehe ich die komplette umformung nicht
lgrizu Auf diesen Beitrag antworten »
RE: erweiterter euklidischer algorithmus
Das ganze ist Rückwärts einsetzen:

99=1*78+21 => 21=99-1*78 I
78=3*21+15 => 15=78-3*21 II
21=1*15+6 => 6=21-1*15 III
15=2*6+3 =>3=15-2*6 IV

Nun beginnen wir bei Zeile IV und setzen immer das blau markierte ein:

3=15-2*6

Eisetzen von Zeile III

3=15-2*(21-1*15)=15-2*21+2*15=3*15-2*21

Einsetzen von Zeile II
3=3*15-2*21=3*(78-3*21)-2*21=3*78-9*21-2*21=3*78-11*21

Einmsetzen von Zeile I

3=3*78-11*21=3*78-11*(99-1*78)=3*78-11*99+11*78=14*78-11*99

Und wir haben eine Linearkombination des ggT
starcraft42 Auf diesen Beitrag antworten »

oh ok jetzt hab ich es endlich verstanden, vielen dank Gott
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »