TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/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{array}{cc}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{array}$

Nun das Ganze wieder in die andere Richung:

$\begin{array}{cc}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{array}$

Daraus ergibt sich nun folgende Gleichung:

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

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