If P is prime, and A is known, what is B such that A*B = 1 mod P?

[NotLKH]

I wanted a function that would return such a result.
After playing around a bit, I dredged up some old contemplations, and was able to code it to work as I expected.

Lets say you wanted to find some number B, such that 7B = 31A+1

That equation can be zeroed to the following:

7B₀-31A₀-1=0

Using modular arithmatic, you can create the following chain:

7B0-31A0-1=0      'Mod this from the 7multiplier, except for 7 itself
7B1-3A0-1=0        'Mod this from the 3multiplier, except for 3 itself
1B1-3A1-1=0        'Since one of the |mults| is now 1, we can now solve for the unknowns

Since the last equation now ends up, unzeroed as:
3A₁ = B₁-1
A₁ can be "assigned" as zero, and B₁ becomes 1

Knowing B₁=1, then the middle equation becomes:
7*1-3A₀-1=0
or...
3A₀ = 6

which results in A₀ = 2

From this, the initial equation becomes:
7B₀-31*2-1=0
or...
B₀ = (63/7) = 9

which, when all is said and done,
9 is the uniary compliment of 7 modular 31
or:
7*9 mod 31 = 1

Now, the following is the VBNet function that achieves this chaining down and back up.

But, I wonder, is there a better way?

Public Function GET_MULT_TO_ONE(ByVal mA As Integer, ByVal mPrime As Integer) As Integer
        Dim mD As Integer
        If Iterate_Mod_To_One(mA, -1 * mPrime, -1, mD, 0) = True Then
            mD = (mD + mPrime) Mod mPrime
            Return mD
        End If
        Return -1
    End Function
    Public Function Iterate_Mod_To_One(ByVal mA As Integer, ByVal mB As Integer, ByVal mC As Integer, ByRef mD As Integer, ByVal mLev As Integer) As Boolean
        mLev = mLev Mod 2
        If mA = 0 Or mB = 0 Or mC = 0 Then
            mD = -1
            Return False
        End If
        'assume user knows what they are doing, ie..
        'initial |mB| is prime,
        'initial |mC| is 1
        'ma will always be positive, mb and mc will always be negative
        'such that X*ma + Y*mb + mc = 0
        If mA = 1 Then
            mD = -1 * mC
            Return True
        End If
        If mB = -1 Then
            mD = mC
            Return True
        End If
 
 
        Dim mA2 As Integer
        Dim mB2 As Integer
        Dim mD2 As Integer
 
        mA2 = mA
        mB2 = mB
 
        Select Case mLev
            Case 0
                mB2 = mB Mod mA
            Case 1
                mA2 = mA Mod mB
        End Select
        If Iterate_Mod_To_One(mA2, mB2, mC, mD, mLev + 1) = True Then
            Select Case mLev
                Case 0
                    mD = -1 * (mB * mD + mC) / mA
                Case 1
                    mD = -1 * (mA * mD + mC) / mB
            End Select
            Return True
        End If
    End Function

And the following is some code illustrating how its used, and that it seems to actually work:

Private Sub MenuItem28_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MenuItem28.Click
        'lets just see if it works for the first 19 primes
 
        Dim MyPrimes() As Integer
        Dim mOutArr() As Integer
        Dim MyI As Integer
        ReDim MyPrimes(19)
        MyPrimes(0) = 2
        MyPrimes(1) = 3
        MyPrimes(2) = 5
        MyPrimes(3) = 7
        MyPrimes(4) = 11
        MyPrimes(5) = 13
        MyPrimes(6) = 17
        MyPrimes(7) = 19
        MyPrimes(8) = 23
        MyPrimes(9) = 29
        MyPrimes(10) = 31
        MyPrimes(11) = 37
        MyPrimes(12) = 41
        MyPrimes(13) = 43
        MyPrimes(14) = 47
        MyPrimes(15) = 53
        MyPrimes(16) = 59
        MyPrimes(17) = 61
        MyPrimes(18) = 67
        MyPrimes(19) = 71
        For MyI = 0 To 19
            Call BUILD_MULT_TO_ONE_FROM_PRIME2(MyPrimes(MyI), mOutArr)
        Next
    End Sub
    Public Sub BUILD_MULT_TO_ONE_FROM_PRIME2(ByVal mPrime As Integer, ByRef mOutArr() As Integer)
        ReDim mOutArr(mPrime - 1)
        Dim MyOutStr As String
        Dim MySeed As Integer
        For MySeed = 0 To mPrime - 1
            mOutArr(MySeed) = -1
        Next
        'so, if good, then
        'MySeed * mOutArr(MySeed) = K => K mod mP = 1
        For MySeed = 0 To mPrime - 1
            mOutArr(MySeed) = GET_MULT_TO_ONE(MySeed, mPrime)
        Next
 
        'now, lets illustrate the results
        MyOutStr = "Prime " & mPrime & ":" & vbTab & "A*B = 1 (mod " & mPrime & " )" & vbCrLf
        For MySeed = 0 To mPrime - 1
            MyOutStr += vbTab & MySeed & "*" & mOutArr(MySeed) & "=" & ((MySeed * mOutArr(MySeed)) Mod mPrime) & vbCrLf
        Next
        MessageBox.Show(MyOutStr)
    End Sub