erweiterter euklidischer algorithmus |
07.03.2012, 17:03 | starcraft42 | Auf diesen Beitrag antworten » |
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 |
||
07.03.2012, 17:16 | 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 |
||
07.03.2012, 17:18 | starcraft42 | Auf diesen Beitrag antworten » |
oh ok jetzt hab ich es endlich verstanden, vielen dank |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|