Problem Statement

From Wikipedia: In modular arithmetic,   the modular multiplicative inverse of an integer   a   modulo   m   is an integer   x   such that Or in other words, such that: It can be shown that such an inverse exists   if and only if   a   and   m   are coprime,   but we will ignore this for this task.

Either by implementing the algorithm, by using a dedicated library or by using a built-in function in your language,   compute the modular inverse of   42 modulo 2017.

Let's start with the solution:

sub inverse($n, :$modulo) {
    my ($c, $d, $uc, $vc, $ud, $vd) = ($n % $modulo, $modulo, 1, 0, 0, 1);
    my $q;
    while $c != 0 {
        ($q, $c, $d) = ($d div $c, $d % $c, $c);
        ($uc, $vc, $ud, $vd) = ($ud - $q*$uc, $vd - $q*$vc, $uc, $vc);
    }
    return $ud % $modulo;
}

say inverse 42, :modulo(2017)