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.




' version 10-07-2018
' compile with: fbc -s console
 
Type ext_euclid
    Dim As Integer a, b
End Type
 
' "Table method" aka "The Magic Box"
Function magic_box(x As Integer, y As Integer) As ext_euclid
 
    Dim As Integer a(1 To 128), b(1 To 128), d(1 To 128), k(1 To 128)
 
    a(1) = 1 : b(1) = 0 : d(1) = x
    a(2) = 0 : b(2) = 1 : d(2) = y : k(2) = x \ y
 
    Dim As Integer i = 2
 
    While Abs(d(i)) <> 1
        i += 1
        a(i) = a(i -2) - k(i -1) * a(i -1)
        b(i) = b(i -2) - k(i -1) * b(i -1)
        d(i) = d(i -2) Mod d(i -1)
        k(i) = d(i -1) \ d(i)
        'Print a(i),b(i),d(i),k(i)
        If d(i -1) Mod d(i) = 0 Then Exit While
    Wend
 
    If d(i) = -1 Then '  -1 * (ab + by) = -1 * -1 ==> -ab -by = 1 
        a(i) = -a(i)
        b(i) = -b(i)
    End If
 
    Function = Type( a(i), b(i) )
 
End Function
' ------=< MAIN >=------
 
Dim As Integer x, y, gcd
Dim As ext_euclid result
 
Do
    Read x, y
    If x = 0 AndAlso y = 0 Then Exit Do
    result = magic_box(x, y)
    With result
        gcd = .a * x + .b * y
        Print "a * "; Str(x); " + b * "; Str(y);  
        Print " = GCD("; Str(x); ", "; Str(y); ") ="; gcd
        If gcd > 1 Then 
            Print "No solution, numbers are not coprime"
        Else 
            Print "a = "; .a; ", b = ";.b
            Print "The Modular inverse of "; x; " modulo "; y; " = ";
            While .a < 0 : .a += IIf(y > 0, y, -y) : Wend 
            Print .a
            'Print "The Modular inverse of "; y; " modulo "; x; " = ";
            'While .b < 0 : .b += IIf(x > 0, x, -x) : Wend 
            'Print .b
        End if
    End With
    Print
Loop
 
Data 42, 2017
Data 40, 1
Data 52, -217
Data -486, 217
Data 40, 2018
Data 0, 0
 
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End