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.




 
(define (modular-multiplicative-inverse a n)
    (if (< n 0)
        (setf n (abs n)))
 
    (if (< a 0)
        (setf a (- n (% (- 0 a) n))))
 
    (setf t 0)
    (setf nt 1)
    (setf r n)
    (setf nr (mod a n))
 
    (while (not (zero? nr))
        (setf q (int (div r nr)))
        (setf tmp nt)
        (setf nt (sub t (mul q nt)))
        (setf t tmp)
        (setf tmp nr)
        (setf nr (sub r (mul q nr)))
        (setf r tmp))
 
    (if (> r 1)
        (setf retvalue nil))
 
    (if (< t 0)
        (setf retvalue (add t n))
        (setf retvalue t))
    retvalue)  
 
(println (modular-multiplicative-inverse 42 2017))
 