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.




# Integer division:
# If $j is 0, then an error condition is raised;
# otherwise, assuming infinite-precision integer arithmetic,
# if the input and $j are integers, then the result will be an integer.
def idivide($j):
  . as $i
  | ($i % $j) as $mod
  | ($i - $mod) / $j ;
 
# the multiplicative inverse of . modulo $n
def modInv($n):
  if $n == 1 then 1
  else . as $this
  | { r   : $n,
      t   : 0,
      newR: length, # abs
      newT: 1}
  | until(.newR == 0;
        .newR as $newR
        | (.r | idivide($newR)) as $q
        | {r   : $newR,
           t   : .newT,
           newT: (.t - $q * .newT),
           newR: (.r - $q * $newR) } )
 
  | if (.r|length) != 1 then "\($this) and \($n) are not co-prime." | error
    else .t
    | if .     < 0 then . + $n
      elif $this < 0 then - .
      else .
      end
    end
  end ;
 
# Example:
42 | modInv(2017)
 