** Using WeBWorK **

PGauxiliaryFunctions.pl has a GreatestCommonDivisor (gcd = gcf) function.
I suggest adding an extended version
      ( d , x , y )  =  xgcd( a , b )
where  gcd(a,b) = d = a x + b y

David Joyner has a concise discussion at
    http://www.usna.edu/Users/math/wdj/book/node14.html
and a Wikipedia article provides more detail
    http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Here is a Perl example
      ( d , x , y , s , t ) = xgcd( a , b)
where  gcd(a,b) = d = a (x + s k) + b (y + t k)  for any integer k
I inserted two lines in definition of xgcd to provide clues for a proof of correctness (hint: Joyner's node13 provides a proof which is easily adapted).  I also made a policy choice to not require inputs to be positive, but I did not trap (a,b)=(0,0) as an error.  (I will also attach the file to this message.)

#!/usr/bin/env perl
#### xgcd.plx    extended Euclidean algorithm    Dick Lane, 2010-06-25
#### gcd(a,b)  =  a (x + s k)  +  b (y + t k)
#### Note: (a,b)=(0,0) is not trapped for special handling.

sub xgcd ($$) {
  my  ($a, $x, $y) = ( int(shift) , 1 , 0 ) ;
  my  ($b, $s, $t) = ( int(shift) , 0 , 1 ) ;

  my ($A,$B) = ($a,$b) ;

  while  ( $b != 0 )  {
    my  $q = int( $a / $b ) ;
    ($a, $x, $y, $b, $s, $t) = ($b, $s, $t, $a-$q*$b, $x-$q*$s, $y-$q*$t);
    print "$a = $A*$x + $B*$y  and  $b = $A*$s + $B*$t\n" ;
  }

  if ($a < 0) {
      return ( -$a, -$x, -$y, $s, $t ) ; }
  else {
      return ( $a, $x, $y, $s, $t ) ;
  }
}

#### prompt for two inputs, compute, summarize result
print "A = " ; $A = <STDIN> ; $A = int($A) ;
print "B = " ; $B = <STDIN> ; $B = int($B) ;
@W  =  xgcd( $A , $B ) ;
print "gcd($A,$B) = $W[0] = $A * ($W[1] + $W[3]*k) + $B * ($W[2] + $W[4]*k)\n";