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

Man finde zwei ganze Zahlen x und y, welche die Gleichung $451x+176y=11$ erfüllen.

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Lösungsvorschlag

Durch kürzen erhält man folgende Gleichung: $41x+16y=1$

Nun wird $ggT(41,16)$ mit Hilfe des Euklidischen Algorithmus bestimmt:

${\begin{aligned}41&=16\cdot 2+9\\16&=9\cdot 1+7\\9&=7\cdot 1+2\\7&=2\cdot 3+1\\2&=1\cdot 2+0\end{aligned}}$

Nun das Ganze wieder in die andere Richung:

${\begin{aligned}1&=7-2\cdot 3\\&=7-(9-7\cdot 1)\cdot 3\\&=4\cdot 7-3\cdot 9\\&=4\cdot (16-9\cdot 1)-3\cdot 9\\&=4\cdot 16-7\cdot 9\\&=4\cdot 16-7\cdot (41-16\cdot 2)\\&=18\cdot 16-7\cdot 41\end{aligned}}$

Daraus ergibt sich nun folgende Gleichung:

${\begin{aligned}-7\cdot 41+18\cdot 16&=1\\-7\cdot 451+18\cdot 176&=11\end{aligned}}$

Das Ergebnis ist: $x=-7$ und $y=18$