From Wikipedia:

In modular arithmetic,   the modular multiplicative inverse of an integer    a    modulo    m    is an integer    x    such that





a

x
≡
1


(
mod

m
)

.


{\displaystyle a\,x\equiv 1{\pmod {m}}.}


Or in other words, such that:





∃
k
∈

Z

,

a

x
=
1
+
k

m


{\displaystyle \exists k\in \mathbb {Z} ,\qquad a\,x=1+k\,m}


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.



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.




include "cowgol.coh";
 
sub mulinv(a: int32, b: int32): (t: int32) is
    if b<0 then b := -b; end if;
    if a<0 then a := b - (-a % b); end if;
    t := 0;
    var nt: int32 := 1;
    var r := b;
    var nr := a % b;
    while nr != 0 loop
        var q := r / nr;
        var tmp := nt; nt := t - q*nt; t := tmp;
        tmp := nr; nr := r - q*nr; r := tmp;
    end loop;
    if r>1 then t := -1;
    elseif t<0 then t := t + b;
    end if;
end sub;
 
record Pair is
    a: int32;
    b: int32;
end record;
 
var data: Pair[] := {
    {42, 2017}, 
    {40, 1}, 
    {52, -217}, 
    {-486, 217}, 
    {40, 2018}
};
 
var i: @indexof data := 0;
while i < @sizeof data loop
    print_i32(data[i].a as uint32);
    print(", ");
    print_i32(data[i].b as uint32);
    print(" -> ");
    var mi := mulinv(data[i].a, data[i].b);
    if mi<0
        then print("no inverse");
        else print_i32(mi as uint32);
    end if;
    print_nl();
    i := i + 1;
end loop;