Perhaps some one can find useful this function to compute the modular inverse of a integer (extended euclidean algorithm): function invmod($a,$b) { $n=$b; $x=0; $lx=1; $y=1; $ly=0; while ($b) { $t=$b; $q=bcdiv($a,$b,0); $b=bcmod($a,$b); $a=$t; $t=$x; $x=bcsub($lx,bcmod(bcmul($q,$x),$n)); $lx=$t; $t=$y; $y=bcsub($ly,bcmod(bcmul($q,$y),$n)); $ly=$t; } if (bccomp($lx,0) == -1) $lx=bcadd($lx,$n); return $lx; } // verify $n="2447995268898324993537772139997802321"; $t="64941057316178801556773346239351236811"; $m="123456789"; $i=invmod($t,$n); // (t*m)*inv(t) is m echo bcmod(bcmul(bcmod(bcmul($t,$m),$n),$i),$n) == $m;