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.




mul_inv = proc (a, b: int) returns (int) signals (no_inverse)
    if b<0 then b := -b end
    if a<0 then a := b - (-a // b) end
    t: int := 0
    nt: int := 1
    r: int := b
    nr: int := a // b
    while nr ~= 0 do
        q: int := r / nr
        t, nt := nt, t - q*nt
        r, nr := nr, r - q*nr
    end
    if r>1 then signal no_inverse end
    if t<0 then t := t+b end
    return(t)
end mul_inv
 
start_up = proc ()
    pair = struct[a, b: int]
    tests: sequence[pair] := sequence[pair]$
       [pair${a: 42, b: 2017},
        pair${a: 40, b: 1},
        pair${a: 52, b: -217},
        pair${a: -486, b: 217},
        pair${a: 40, b: 2018}]
 
    po: stream := stream$primary_output()
    for test: pair in sequence[pair]$elements(tests) do
        stream$puts(po, int$unparse(test.a) || ", "
                     || int$unparse(test.b) || " -> ")
        stream$putl(po, int$unparse(mul_inv(test.a, test.b)))
        except when no_inverse:
            stream$putl(po, "no modular inverse")
        end 
    end
end start_up