using System;

using System.Numerics;

​

//https://stackoverflow.com/questions/66645125/how-to-perform-multiplicative-inverse-in-c-sharp

//https://stackoverflow.com/questions/7483706/c-sharp-modinverse-function

​

public static class BigIntegerModExt 

{

    public 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);

    }

    public static BigInteger ModInversion(this 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;

    }

​

    public static BigInteger ModDivision(

      this BigInteger left, BigInteger right, BigInteger modulo) =>

           (left * ModInversion(right, modulo)) % modulo;

}

​

public class Program

{   

    public static void Main()

    {   

        BigInteger b = new BigInteger(12345678912345678912);

​

        //DONE: Please, note that ^ stands for XOR, so 2 ^ 64 == 66

        BigInteger mod = BigInteger.Pow(2, 64);

​

        var modedInteger = b * 3712931 % mod;

​

        BigInteger result = modedInteger.ModDivision(3712931, mod);

​

        Console.WriteLine(result);

        Console.WriteLine("***********************************");

        //DONE: Please, note that ^ stands for XOR, so 2 ^ 64 == 66

        BigInteger z = BigInteger.Pow(2, 64);

        BigInteger x = new BigInteger(3456789123456789345);

        BigInteger y = new BigInteger(3456789123456789345);

        var xyModInt = x * y % z;

​

        BigInteger resultX = xyModInt.ModDivision(y, z);

​

        Console.WriteLine(xyModInt);

        Console.WriteLine(resultX);

        Console.WriteLine(resultX == x);

    }

}