In dieser Aufgabe soll eine lineare Gleichung mit zwei Variablen, deren Koeffizienten und rechte Seite ganzzahlig sind, gelöst werden. Ziel ist es, eine ganzzahlige Lösung für die Variablen zu finden, indem der erweiterte Euklidische Algorithmus angewendet wird. Dafür wird zunächst der größte gemeinsame Teiler der Koeffizienten mithilfe des Euklidischen Algorithmus berechnet und anschließend die Gleichung als Linearkombination dargestellt.
Beispiel
Bestimmen Sie für die Gleichung \[ 114X + 31Y = 1\]eine ganzahlige Lösung \( ( x_0; y_0) \) mittels des erweiterten Euklidischen Algorithmus.
a) Führen Sie den Euklidischen Algorithmus zur Berechnung von ggT(114;31) aus.
\[
\begin{array}{crclll}
\end{array}
\]
b) Wie lautet die Lösung?
\( (x_0,y_0) = \)
Formate
Stichworte
erweiterter euklidischer algorithmus, diophantische gleichung, ganzzahlige lösungen, größter gemeinsamer teiler, linearkombination, algorithmen, zahlentheorie