Euklidischer Algorithmus/Darstellung des ggT/52 und 30/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}}$