proc eggT (int a, int b)
"USAGE:      eggT(a,b); int a, int b
ASSUME:      a und b sind beide nicht Null
RETURN:      list, [ggT(a,b),p,q] mit ggT(a,b)=p*a+q*b
KEYWORDS:    groesster gemeinsamer Teiler, erweiterter Euklidischer Algorithmus
EXAMPLE:     ggT;   zeigt ein Beispiel"
{
  int q,r;        // Variablen fuer Division mit Rest
  list d;         // nimmt Ergebnisse in der Rekursion auf 
  // Falls a==0 (bzw. b==0), dann ist der ggT(a,b)=b und b=0*a+1*b (bzw. ggT(a,b)=a und a=1*a+0*b)
  if ((a==0) or (b==0))
  {
    "Eine der eingegebenen Zahlen ist 0!";
    return (list(0,0,0))
  }
  else
  {
    // r = Rest bei Division mit Rest von a durch b 
    r=a mod b;
    // q = Anteil von b in a bei Division mit Rest von a durch b (d.h. a=q*b+r)
    q=a div b;
    // Falls r==0, ...
    if (r==0)
    {
      // ... dann ist -b=ggT(a,b) und ggT=0*a-1*b, falls b<0, und ...
      if (b<0)
      {
        d=-b,0,-1;
      }
      // ... dann ist b=ggT(a,b) und ggT=0*a+1*b, falls b>0, und ...
      else
      {
        d=b,0,1;
      }
    }
    // ... sonst rufen wir die Prozedur rekursiv mit b und r auf, ...
    else
    {
      d=eggT(b,r);
      // ... und es gilt (mit ggf. vertauschtem a und b) ggT(b,r)= d[3]*a+(d[2]-q*d[3])*b.
      d=d[1],d[3],d[2]-q*d[3];    
    }
  }
  return(d);
}
example
{
  "BEISPIEL";
  echo=2;
  list l;
  l=eggT(100,44);
  l[1];
  l[1]-(l[2]*100+l[3]*44);
  l=eggT(44,100);
  l[1];
  l[1]-(l[2]*44+l[3]*100);
  l=eggT(-100,44);
  l[1];
  l[1]-(l[2]*(-100)+l[3]*44);
  l=eggT(44,-100);
  l[1];
  l[1]-(l[2]*44+l[3]*(-100));
  l=eggT(-100,-44);
  l[1];
  l[1]-(l[2]*(-100)+l[3]*(-44));
  l=eggT(-44,-100);
  l[1];
  l[1]-(l[2]*(-44)+l[3]*(-100));
  l=eggT(100,-44);
  l[1];
  l[1]-(l[2]*100+l[3]*(-44));
  eggT(2,0);
}

proc ggT (int a, int b)
"USAGE:      ggT(a,b); int a, int b
ASSUME:      a und b sind beide nicht Null
RETURN:      int, groesster gemeinsamer Teiler von a und b
KEYWORDS:    groesster gemeinsamer Teiler, erweiterter Euklidischer Algorithmus
EXAMPLE:     ggT;   zeigt ein Beispiel"
{
  int r;        // Variable fuer den Rest
  // Falls a==0 (bzw. b==0), dann soll eine Fehlermeldung ausgegeben werden.
  if ((a==0) or (b==0))
  {
    "Eine der eingegebenen Zahlen ist 0!";
    return (0)
  }
  else
  {
    // Falls Betrag(a)<Betrag(b), dann tausche a und b aus.    
    if (((a<0) and (b<a)) or ((a>0) and (b>a)))
    {
      int z=a;
      a=b;
      b=z;
    }
    // r = Rest bei Division mit Rest von a durch b 
    r=a mod b;
    // Falls r==0, ...
    while (r>0)
    {
      a=b;
      b=r;
      r=a mod b;
    }
    return(b);
  }
}
example
{
  "BEISPIEL";
  echo=2;
  ggT(100,44);
  ggT(44,100);
  ggT(-100,44);
  ggT(44,-100);
  ggT(-100,-44);
  ggT(-44,-100);
  ggT(100,-44);
  ggT(2,0);
}