## WeBWorK Problems

### extended Euclidean algorithm

by Dick Lane -
Number of replies: 0
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";