TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 58

Aus VoWi
Zur Navigation springen Zur Suche springen

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

Angabe[Bearbeiten]

Lösungsvorschlag[Bearbeiten]

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

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


\begin{align}
41 & = 16\cdot2+9\\
16 & = 9\cdot1+7\\
9 & = 7\cdot1+2\\
7 & = 2\cdot3+1\\
2 & = 1\cdot2+0
\end{align}

Nun das Ganze wieder in die andere Richung:


\begin{align}
1 & = 7 - 2\cdot3\\
 & = 7-(9-7\cdot1)\cdot3\\
 & = 4\cdot7-3\cdot9\\
 & = 4\cdot(16-9\cdot1)-3\cdot9\\
 & = 4\cdot16-7\cdot9\\
 & = 4\cdot16-7\cdot(41-16\cdot2)\\
 & = 18\cdot16-7\cdot41
\end{align}

Daraus ergibt sich nun folgende Gleichung:


\begin{align}
-7\cdot41+18\cdot16 & = 1\\
-7\cdot451+18\cdot176 & = 11
\end{align}

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