How do I find the inverse of a MOD function

**christopher2222** · 01-01-2008, 03:10 PM

I'm trying to find out how to do the inverse of a MOD function.

7mod(23) = 7 That's easy enough in excel to do =MOD(7,23)

However the inverse of 7mod(23) = 10 I haven't found a way to compute the inverse of a mod function with excel.

Does anyone out there know how to do it?

**mikerickson** · 01-01-2008, 03:12 PM

Because you can't

If Mod(x,7)=3, x could be 3,10,17,....

Mod has no inverse.

**christopher2222** · 01-01-2008, 03:32 PM

You are right that MOD(x,7) x has multiple values however you are wrong that mod has no inverse.

Maybe I need to be more explicit. Some values for mod have no inverses but for the ones that do I want excel to calculate them.

MOD(7,23) has 10 as it's inverse.

As an example I will calculate a column of values for MOD(x,23) x=1..10 and I will get a consecutive set of numbers 1 to 10. Now the next column will show the inverses for MOD(x,23) where x has a value from one to ten. I SHOULD get 1, 12, 8, 6, 14, 4, 10, 3, 18, and 7 as each of their inverses. How do I get excel to calculate these for me.

Mathematics programs can easily calculate these values.

**shg** · 01-01-2008, 05:40 PM

Try this:

Function ModInv(b As Long, m As Long) As Variant
    ' Returns the modular inverse of b Mod m using the
    ' Extended Euclidean Algorithm to compute integers x and y
    ' {x, y || b * x + m * y = GCD(b, m) == 1 (else the inverse does not exist)}
    ' i.e., Mod(x * b, m) = 1
    ' Algorithm from Junaid Majeed at
    ' http://www.codeproject.com/KB/recipes/eealgo.aspx

    Dim ak As Long, ak1 As Long, ak2 As Long
    Dim xk As Long, xk1 As Long, xk2 As Long
    Dim yk As Long, yk1 As Long, yk2 As Long
    Dim qk As Long, qk1 As Long, qk2 As Long

    If Abs(GCD(b, m)) <> 1 Then
        ModInv = CVErr(xlErrValue)
        Exit Function
    Else
        ak1 = b
        xk1 = 1
        yk1 = 0

        ak = m
        xk = 0
        yk = 1
        qk = Int(ak1 / ak)

        Do
            ak2 = ak1: ak1 = ak
            xk2 = xk1: xk1 = xk
            yk2 = yk1: yk1 = yk
            qk2 = qk1: qk1 = qk
            
            ak = ak2 - qk1 * ak1
            If ak = 0 Then Exit Do
            
            xk = xk2 - qk1 * xk1
            yk = yk2 - qk1 * yk1
            qk = Int(ak1 / ak)
        Loop
    End If
    ModInv = xk1
End Function

Function GCD(ByVal i1 As Long, ByVal i2 As Long) As Long
    If i2 = 0 Then
        GCD = i1
    Else
        GCD = GCD(i2, i1 Mod i2)
    End If
End Function

**mikerickson** · 01-01-2008, 07:55 PM

Now , I understand

The multiplicitive inverse. Given A and N, find B such that Mod(A*B,N)=1.

**christopher2222** · 01-01-2008, 09:06 PM

Yes! That's exactly it, the multiplicative inverse. Sorry I was a little vague in the beginning.

And thanks for the code!

I guess there isn't any other way to do it without using some sort of code programming is there?

**Glenn Kennedy** · 10-02-2022, 06:15 AM

I, too, know it's old... but is it correct???

https://www.geeksforgeeks.org/multip...nder-modulo-m/

In which case, it should be:

=MATCH(1,INDEX(MOD($A$1*ROW(INDIRECT("1:"&$B$1)),$B$1),0),0)

or (O365)

=MATCH(1,MOD($A$1*SEQUENCE($B$1),$B$1),0)

**Dave Keenan** · 10-02-2022, 08:18 AM

Hi Glen. Daddylonglegs made it clear that for his formula, the modulus was in A1 and the other argument was in B1. That gives correct results for moduli greater than 1. And with my wrapper, it gives correct results modulo 1 and for negative moduli as well, as checked against ModularInverse[] in Wolfram Language.

You seem to have merely swapped the arguments, but you haven't said which one is the modulus.