TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 57

Aus VoWi
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