Solving modulo in c#

Question

I'm having troubles solving modulo in c#. The example below

7^-1 modulo 26

when on Wolfram Alpha returns correct 15. In c# when I tried direct:

1/7 % 26

it returns unwanted 0.142857142857143 instead of desired 15. But i'm not a master mathematician, so i'm probably missing something vital.

Answer 1

Your are looking for modular inversion: in case of

7**-1 modulo 26 = x

or

1 / 7 modulo 26 = x 

you actually want to find out an x such that

(x * 7) modulo 26 = 1

In our case x == 15 since

 15 * 7 == 105 == 26 * 4 + 1

For small modulo values (like 26) you can find the answer (15) with a help of naive for loop:

  int modulo = 26;
  int div = 7;
  int result = 0;
  
  for (int i = 1; i < modulo; ++i)
    if ((i * div) % modulo == 1) {
      result = i;

      break;
    }

  Console.Write(result);

In general case, you can obtain the result with a help of Extended Euclid Algorithm. Often, when working with modulo arithmetics we face huge numbers, that's why let me show the code for BigInteger; if it's not your case you can turn BigInteger to good old int.

Code:

using System.Numerics;
...
private static (BigInteger LeftFactor,
                BigInteger RightFactor,
                BigInteger Gcd) Egcd(this BigInteger left, BigInteger right) {
  BigInteger leftFactor = 0;
  BigInteger rightFactor = 1;

  BigInteger u = 1;
  BigInteger v = 0;
  BigInteger gcd = 0;

  while (left != 0) {
    BigInteger q = right / left;
    BigInteger r = right % left;

    BigInteger m = leftFactor - u * q;
    BigInteger n = rightFactor - v * q;

    right = left;
    left = r;
    leftFactor = u;
    rightFactor = v;
    u = m;
    v = n;

    gcd = right;
  }

  return (LeftFactor: leftFactor,
          RightFactor: rightFactor,
          Gcd: gcd);
}

The inversion itself will be

private static BigInteger ModInversion(BigInteger value, BigInteger modulo) {
  var egcd = Egcd(value, modulo);

  if (egcd.Gcd != 1)
    throw new ArgumentException("Invalid modulo", nameof(modulo));

  BigInteger result = egcd.LeftFactor;

  if (result < 0)
    result += modulo;

  return result % modulo;
}

Demo:

using System.Numerics;

...

BigInteger result = ModInversion(7, 26);

Console.Write(result);

Outcome:

15