(Lemma von Bézout)
Seien a, b
0.
Der größte gemeinsame Teiler ggt(a, b) lässt sich als ganzzahlige Linearkombination von a und b darstellen:
ggt(a, b) = u·a + v·b mit u, v
Die Darstellung ist nicht eindeutig; die Gleichung wird durch verschiedene Zahlenpaare u, v erfüllt.
Der erweiterte euklidische Algorithmus berechnet zusätzlich noch eine Darstellung von ggt(a, b) als ganzzahlige Linearkombination von a und b.
Er berechnet den größten gemeinsamen Teiler g zweier Zahlen a und b und zusätzlich die Koeffizienten u und v einer Darstellung von g als ganzzahlige Linearkombination.
Recursion
function extgcd(a, b) {
if (b == 0) {
return [a, 1, 0]
} else {
guv = extgcd(b, a % b);
return [guv[0], guv[2], guv[1] - parseInt(a / b) * guv[2]]
}
}
Iteration
function extgcd(a, b) {
a,b, u = 1; v = 0; s = 0; t = 1;
do {
q = parseInt(a / b);
tmp = b; b = a - q * b; a = tmp;
tmp = s; s = u - q * s; u = tmp;
tmp = t; t = v - q * t; v = tmp;
} while (b != 0)
return [a, u, v]
};
ab = extgcd(99, 78);
[3,-11,14]
CAS (2) per Iterationlist (a,b,u,v,s,t):
n einstellen, so das Divisor 2.Spalte 0 wird!
