Erweiterter Euklidischer Algorithmus |
| 03.11.2018, 17:52 | Adramelec | Auf diesen Beitrag antworten » |
| Erweiterter Euklidischer Algorithmus für folgende Zahlen soll ich den erweiterten euklidischen Algorithmus anwenden: 63 und 9. Gut, ich lege los: "normaler" euklidischer Algorithmus: Fertig. ggT(9). Nun muss ich den erweiterten anwenden, aber wie schreibe ich das nun richtig an? Die Lösung ist offensichtlich mit . (Wenn ich beim Algorithmus mindestens zwei Zeilen rausbekomme, ist es auch kein Problem, da ich ja hier dann substituieren kann - aber diese eine Zeile irritiert mich etwas). Ich hoffe es ist klar, was hier mein Problem ist und eventuell kann mir da jemand auf die Sprünge helfen? :-) |
||
| 03.11.2018, 18:01 | HAL 9000 | Auf diesen Beitrag antworten » |
Der Fall, dass nach dem ersten Schritt schon Schluss ist, kommt nur dann vor, wenn die zweite Ausgangszahl ein Teiler der ersten Zahl ist, und damit ist diese Zahl natürlich auch der ggT, und es ist . Bei entsprechender Organisation des EEA ist das kein extra zu betrachtender Sonderfall, sondern ergibt sich automatisch durch den Algorithmus, z.B. bei der iterativen Variante des EEA. |
||
| 03.11.2018, 18:21 | Adramelec | Auf diesen Beitrag antworten » |
Danke - das waren alle Hinweise die ich brauchte! |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
