I don't suppose anyone here knows php and modular arithmetic well enough to tell me what is wrong with my modular inversion code... It works with positive values, but not negative values.

function egcd($a, $b){

$x = 0;

$y = 1;

$u = 1;

$v = 0;

while($a != 0){

$q = bcdiv($b, $a);

$r = bcmod($b, $a);

$m = bcsub($x, bcmul($u, $q));

$n = bcsub($y, bcmul($v, $q));

$b = $a;

$a = $r;

$x = $u;

$y = $v;

$u = $m;

$v = $n;

}

return array($b, $x, $y);

}

function modinv($a, $m){

list($g, $x, $y) = egcd($a, $m);

if($g != 1){

return "modular inverse doesn't exist";

}else{

return bcmod($x, $m);

}

}

So, modinv(-5, 17) returns "modular inverse doesn't exist". It should return 10. (That is the correct answer to -5

^{-1} mod 17.)

Thanks.