Euklidischer Algorithmus/Z/Darstellung des ggT/Textabschnitt

Mit dem euklidischen Algorithmus kann man auch durch Zurückrechnen eine Darstellung des größten gemeinsamen Teilers als Linearkombination der beiden vorgegebenen Zahlen erhalten. Dazu seien

r_{i} = q_{i} r_{i + 1} + r_{i + 2}

die Gleichungen im euklidischen Algorithmus und $r_{k - 1} = ggT (r_{0}, r_{1})$ . Aus der letzten Gleichung

r_{k - 3} = q_{k - 3} r_{k - 2} + r_{k - 1}

erhält man die Darstellung

r_{k - 1} = r_{k - 3} - q_{k - 3} r_{k - 2}

von $r_{k - 1}$ als Linearkombination mit $r_{k - 3}$ und $r_{k - 2}$ . Mit der vorhergehenden Zeile

r_{k - 4} = q_{k - 4} r_{k - 3} + r_{k - 2}

bzw.

r_{k - 2} = r_{k - 4} - q_{k - 4} r_{k - 3}

kann man in dieser Darstellung $r_{k - 2}$ ersetzen und erhält eine Darstellung von $r_{k - 1}$ als Linearkombination von $r_{k - 3}$ und $r_{k - 4}$ . So fortfahrend erhält man schließlich eine Darstellung von

r_{k - 1} = ggT (r_{0}, r_{1})

als Linearkombination von $r_{0}$ und $r_{1}$ .

Beispiel

Wir wollen für $52$ und $30$ eine Darstellung des größten gemeinsamen Teilers finden. Wir führen dazu den euklidischen Algorithmus durch.

52 = 1 \cdot 30 + 22

30 = 1 \cdot 22 + 8

22 = 2 \cdot 8 + 6

8 = 1 \cdot 6 + 2

6 = 3 \cdot 2 + 0.

D.h. $2$ ist der größte gemeinsame Teiler von $52$ und $30$ . Rückwärts gelesen erhält man daraus die Darstellung

\begin{matrix} 2 & = 8 - 6 \\ = 8 - (22 - 2 \cdot 8) \\ = 3 \cdot 8 - 22 \\ = 3 \cdot (30 - 22) - 22 \\ = 3 \cdot 30 - 4 \cdot 22 \\ = 3 \cdot 30 - 4 \cdot (52 - 30) \\ = 7 \cdot 30 - 4 \cdot 52. \end{matrix}