(Erweiterter) Euklidischer Algorithmus

Eingabe: natürliche Zahlen a, b.
// Vorbedingung: a = A und b = B
nat c = 1, nat d = 0; nat e = 0; nat f = 1;
// Invariante: ggt(a,b) = ggt(A,B)
//   und A*c + B*d = a  und  A*e + B*f = b
while (a ungleich b) {
     if (a > b) {
         ...
     } else {
         ...
}    }
// Nachbedingung: A*c + B*d = ggt(A,B)
Ausgabe: c, d