An implementation of the extended euclidean algorithm.

ExtGCD.frm

**
* The extended euclidean algorithm, which gives x and y such that
*   a*x + b*y = gcd(a, b) >= 0.
* Input: Integers $a and $b.
* Output: Integers $x and $y.
*
#procedure ExtGCD(a,b,x,y,tmp1,tmp2,tmp3,tmp4,tmp5,tmp6)
  #define aa    "`tmp1'"
  #define bb    "`tmp2'"
  #define lastx "`tmp3'"
  #define lasty "`tmp4'"
  #define q     "`tmp5'"
  #define tmp   "`tmp6'"
  $`aa' = abs_($`a');
  $`bb' = abs_($`b');
  $`x' = 0;
  $`y' = 1;
  $`lastx' = 1;
  $`lasty' = 0;
  $`tmp' = termsin_($`bb');
  while ($`tmp');
    $`q' = integer_($`aa'/$`bb');

    $`tmp'   = $`bb';
    if ($`bb' == 1);
      $`bb'  = 0;  * a workaround of mod_(n?,1).
    else;
      $`bb'  = mod_($`aa',$`bb');
    endif;
    $`aa'    = $`tmp';

    $`tmp'   = $`x';
    $`x'     = $`lastx' - $`q'*$`x';
    $`lastx' = $`tmp';

    $`tmp'   = $`y';
    $`y'     = $`lasty' - $`q'*$`y';
    $`lasty' = $`tmp';

    $`tmp' = termsin_($`bb');
  endwhile;
  $`x' = sig_($`a')*$`lastx';
  $`y' = sig_($`b')*$`lasty';
#endprocedure

* Test

#$a =  244309253330115;
#$b = -222043931593200;
#$dummy = 1;
#inside $dummy
  #call ExtGCD(a,b,x,y,tmp1,...,tmp6)
#endinside

L F = dum_($a,$b,$x,$y,$a*$x+$b*$y,abs_(gcd_($a,$b)));
Format nospaces;
P;
.end

* The answer must be (244309253330115,-222043931593200,2243768619423,2468761168673,45,45);