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.




PROGRAM MOD_INV
 
!$INTEGER
 
PROCEDURE MUL_INV(A,B->T)
  LOCAL NT,R,NR,Q,TMP
  IF B<0 THEN B=-B
  IF A<0 THEN A=B-(-A MOD B)
  T=0  NT=1  R=B  NR=A MOD B
  WHILE NR<>0 DO
      Q=R DIV NR
      TMP=NT  NT=T-Q*NT  T=TMP
      TMP=NR  NR=R-Q*NR  R=TMP
  END WHILE
  IF (R>1) THEN T=-1 EXIT PROCEDURE  ! NO INVERSE
  IF (T<0) THEN T+=B
END PROCEDURE
 
 
BEGIN
     MUL_INV(42,2017->T) PRINT(T)
     MUL_INV(40,1->T) PRINT(T)
     MUL_INV(52,-217->T) PRINT(T)    ! pari semantics for negative modulus
     MUL_INV(-486,217->T)  PRINT(T)
     MUL_INV(40,2018->T) PRINT(T)
END PROGRAM
 