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.




 
def gcdExt(u: Int, v: Int): (Int, Int, Int) = {
  @tailrec
  def aux(a: Int, b: Int, x: Int, y: Int, x1: Int, x2: Int, y1: Int, y2: Int): (Int, Int, Int) = {
    if(b == 0) (x, y, a) else {
      val (q, r) = (a / b, a % b)
      aux(b, r, x2 - q * x1, y2 - q * y1, x, x1, y, y1)
    }
  }
  aux(u, v, 1, 0, 0, 1, 1, 0)
}
 
def modInv(a: Int, m: Int): Option[Int] = {
  val (i, j, g) = gcdExt(a, m)
  if (g == 1) Option(if (i < 0) i + m else i) else Option.empty
}