TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 57
Zur Navigation springen
Zur Suche springen
Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)
Hilfreiches[Bearbeiten | Quelltext bearbeiten]
Satz 1.18 aus dem Buch Mathematik für Informatik:
Ist d der größte gemeinsame Teiler der von Null verschiedenen ganzen Zahlen a, b, so gibt es ganze Zahlen e, f mit
ea + fb = d, die mit Hilfe der Divisionskette des Euklidischen Algorithmus von a und b effektiv berechnet werden können.
Lösung(svorschlag)[Bearbeiten | Quelltext bearbeiten]
von --Christian.abila 15:39, 17. Jul. 2012 (CEST)
243 = 198 * 1 + 45
198 = 45 * 4 + 18
45 = 18 * 2 + 9
18 = 9 * 2 + 0
9 = 45 - 18 * 2
9 = 45 - (198 - 45 * 4) * 2
= 45 - 198 * 2 + 45 * 8
= 45 * 9 - 198 * 2
= (243 - 198 * 1) * 9 - 198 * 2
= 243 * 9 - 198 * 9 - 198 * 2
= 243 * 9 - 198 * 11
gleich wie oben aber mit Zeilenumbrüche formatiert:
9 = 45 - 18 * 2
9 = 45 - (198 - 45 * 4) * 2
= 45 - 198 * 2 + 45 * 8
= 45 * 9 - 198 * 2
= (243 - 198 * 1) * 9 - 198 * 2
= 243 * 9 - 198 * 9 - 198 * 2
= 243 * 9 - 198 * 11
Lösung: x = 9, y = -11