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.





10 ' Modular inverse
20 LET E% = 42
30 LET T% = 2017
40 GOSUB 1000
50 PRINT MODINV%
60 END

990  ' increments e stp (step) times until bal is greater than t
992  ' repeats until bal = 1 (mod = 1) and returns count
994  ' bal will not be greater than t + e 
1000 LET D% = 0
1010 IF E% >= T% THEN GOTO 1140
1020  LET BAL% = E%
1025  ' At least one iteration is necessary
1030  LET STP% = ((T% - BAL%) \ E%) + 1
1040  LET BAL% = BAL% + STP% * E%
1050  LET COUNT% = 1 + STP%
1060  LET BAL% = BAL% - T%
1070  WHILE BAL% <> 1
1080   LET STP% = ((T% - BAL%) \ E%) + 1
1090   LET BAL% = BAL% + STP% * E%
1100   LET COUNT% = COUNT% + STP%
1110   LET BAL% = BAL% - T%
1120  WEND
1130  LET D% = COUNT%
1140 LET MODINV% = D%
1150 RETURN
 