This subroutine calculates the multiplicative inverse of a number modulo another one. This is similar to the modinv method in Math::BigInt, but that one seems to be only for big numbers. This one works with friendly small numbers too.

Calling is $b = divmod($a, $m) where $a, $m are two relatively prime positive integers. Then, $b in an integer so that ($a * $b) % $m == 1.

For example, divmod(17, 26) returns 23, as (17 * 23) % 26 == 1.

use warnings; 
use strict; 
sub divmod { 
        my($a, $m) = @_; my($b, $x, $y, $n) = ($m, 1, 0);
        while (0 != $a) { $n = int($b / $a); ($a, $b, $x, $y) = ($b - $n * $a, $a, $y - $n * $x, $x); } 
        $y % $m; 
}