Hilfsmittel: erweiterter Euklid

Satz: wenn g = ggT(a, b), dann gibt es Zahlen c, d mit ac + bd = g.

c = 1; d = 0; e = 0; f = 1;
while (b > 0) {
   // c*a0 + d*b0 = a und e*a0 + f*b0 = b
   q = a / b; r = a % b; // resultat, rest
   a = b; b = r;
   e' = c - q*e; c = e; e = e';
   f' = d - q*f; d = f; f = f';
}

40 : 7 = 5 R 5    5 = 40 - 5*7
 7 : 5 = 1 R 2    2 = 7  -   5 = -40 + 6*7
 5 : 2 = 2 R 1    1 = 5  - 2*2 = 5*40 - 17*7