' 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