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.




get "libhdr"
 
let mulinv(a, b) =
    b<0 -> mulinv(a, -b),
    a<0 -> mulinv(b - (-a rem b), b),
    valof
    $(  let t, nt, r, nr = 0, 1, b, a rem b
        until nr = 0
        $(  let tmp, q = ?, r / nr
            tmp := nt ; nt := t - q*nt ; t := tmp
            tmp := nr ; nr := r - q*nr ; r := tmp
        $)
        resultis r>1 -> -1, 
                 t<0 -> t + b, 
                 t
    $)
 
let show(a, b) be
$(  let mi = mulinv(a, b)
    test mi>=0 
        do writef("%N, %N -> %N*N", a, b, mi)
        or writef("%N, %N -> no inverse*N", a, b)
$)
 
let start() be
$(  show(42, 2017)
    show(40, 1)
    show(52, -217)
    show(-486, 217)
    show(40, 2018)
$)