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}=\operatorname {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}=\operatorname {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{aligned}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{aligned}}$