```// ************************************************************************** //
//                                                                            //
//    eses                   eses                                             //
//   eses                     eses                                            //
//  eses    eseses  esesese    eses   Embedded Systems Group                  //
//  ese    ese  ese ese         ese                                           //
//  ese    eseseses eseseses    ese   Department of Computer Science          //
//  eses   eses          ese   eses                                           //
//   eses   eseses  eseseses  eses    University of Kaiserslautern            //
//    eses                   eses                                             //
//                                                                            //
// ************************************************************************** //
// The function below computes the greatest common divisor using the extended
// Euclidean algorithm. In addition to the greatest common divisor g of two
// numbers a,b it also computes numbers s,t such that g = s*a + t*b holds.
// ************************************************************************** //

function extendedEuclid(nat a,b) : nat {
nat q,r,s,t,old_r,old_s,old_t,y;
r = b;
s = 0;
t = 1;
old_r = a;
old_s = 1;
old_t = 0;
while(r!=0) {
q = old_r / r;
y = r;
r = old_r - q * r;
old_r = y;
y = s;
s = old_s - q * s;
old_s = y;
y = t;
t = old_t - q * t;
old_t = y;
}
return old_r;
}