C# ModInverse Function

Since .Net 4.0+ implements BigInteger with a special modular arithmetics function ModPow (which produces “X power Y modulo Z”), you don't need a third-party library to emulate ModInverse. If n is a prime, all you need to do is to compute:

a_inverse = BigInteger.ModPow(a, n - 2, n)

For more details, look in Wikipedia: Modular multiplicative inverse, section Using Euler's theorem, the special case “when m is a prime”. By the way, there is a more recent SO topic on this: 1/BigInteger in c#, with the same approach suggested by CodesInChaos.

int modInverse(int a, int n) 
{
    int i = n, v = 0, d = 1;
    while (a>0) {
        int t = i/a, x = a;
        a = i % x;
        i = x;
        x = d;
        d = v - t*x;
        v = x;
    }
    v %= n;
    if (v<0) v = (v+n)%n;
    return v;
}

The BouncyCastle Crypto library has a BigInteger implementation that has most of the modular arithmetic functions. It's in the Org.BouncyCastle.Math namespace.

Here is a slightly more polished version of Samuel Allan's algorithm. The TryModInverse method returns a bool value, that indicates whether a modular multiplicative inverse exists for this number and modulo.

public static bool TryModInverse(int number, int modulo, out int result)
{
    if (number < 1) throw new ArgumentOutOfRangeException(nameof(number));
    if (modulo < 2) throw new ArgumentOutOfRangeException(nameof(modulo));
    int n = number;
    int m = modulo, v = 0, d = 1;
    while (n > 0)
    {
        int t = m / n, x = n;
        n = m % x;
        m = x;
        x = d;
        d = checked(v - t * x); // Just in case
        v = x;
    }
    result = v % modulo;
    if (result < 0) result += modulo;
    if ((long)number * result % modulo == 1L) return true;
    result = default;
    return false;
}