.cs

public static class ExtendedGCD
{
    #region General

    /// <summary>
    /// Остаток от деления, как в Питоне
    /// </summary>
    /// <param name="a"></param>
    /// <param name="p"></param>
    /// <returns></returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static BigInteger PythonMod(BigInteger a, BigInteger p)
    {
        return ((a % p) + p) % p;
    }

    #endregion

    #region out

    public static BigInteger CalcWithOut(BigInteger a, BigInteger prime, out BigInteger x, out BigInteger y)
    {
        if (a == 0)
        {
            x = 0;
            y = 1;
            return prime;
        }

        var gcd = CalcWithOut(prime % a, a, out var x1, out var y1);
        x = y1 - (prime / a) * x1;
        y = x1;
        return gcd;
    }

    public static BigInteger FindWithOut(BigInteger a, BigInteger prime)
    {
        var gcd = CalcWithOut(a, prime, out var x, out _);
        if (gcd == 1)
        {
            return PythonMod(x, prime);
        }

        throw new ArgumentException("Обратного элемента не существует, т.к. a и p не взаимно просты.");
    }

    #endregion

    #region SystemTuple

    // ReSharper disable once UnusedTupleComponentInReturnValue
    public static (BigInteger x, BigInteger y, BigInteger prime) CalcWithSystemTuple(BigInteger a, BigInteger prime)
    {
        if (a == 0)
        {
            return (BigInteger.Zero, BigInteger.Zero, prime);
        }

        var gcd = CalcWithOut(prime % a, a, out var x1, out var y1);
        var x = y1 - (prime / a) * x1;
        // ReSharper disable once InlineTemporaryVariable
        var y = x1;

        return (x, y, gcd);
    }

    public static BigInteger FindWithSystemTuple(BigInteger a, BigInteger prime)
    {
        var (x, _, gcd) = CalcWithSystemTuple(a, prime);
        if (gcd == 1)
        {
            return PythonMod(x, prime);
        }

        throw new ArgumentException("Обратного элемента не существует, т.к. a и p не взаимно просты.");
    }

    #endregion

    #region Tuple

    // ReSharper disable once UnusedTupleComponentInReturnValue
    public static Tuple<BigInteger, BigInteger, BigInteger> CalcWithTuple(BigInteger a, BigInteger prime)
    {
        if (a == 0)
        {
            return new Tuple<BigInteger, BigInteger, BigInteger>(BigInteger.Zero, BigInteger.Zero, prime);
        }

        var gcd = CalcWithOut(prime % a, a, out var x1, out var y1);
        var x = y1 - (prime / a) * x1;
        // ReSharper disable once InlineTemporaryVariable
        var y = x1;

        return new Tuple<BigInteger, BigInteger, BigInteger>(x, y, gcd);
    }

    public static BigInteger FindWithTuple(BigInteger a, BigInteger prime)
    {
        var item = CalcWithTuple(a, prime);
        if (item.Item3 == 1)
        {
            return PythonMod(item.Item1, prime);
        }

        throw new ArgumentException("Обратного элемента не существует, т.к. a и p не взаимно просты.");
    }

    #endregion

    #region anonymous type

    // ReSharper disable once UnusedTupleComponentInReturnValue
    public static dynamic CalcWithAnonymous(BigInteger a, BigInteger prime)
    {
        if (a == 0)
        {
            return new { x = BigInteger.Zero, y = BigInteger.Zero, gcd = prime };
        }

        var gcd = CalcWithOut(prime % a, a, out var x1, out var y1);
        var x = y1 - (prime / a) * x1;
        // ReSharper disable once InlineTemporaryVariable
        var y = x1;

        return new { x = x, y = y, gcd = gcd };
    }

    public static BigInteger FindWithAnonymous(BigInteger a, BigInteger prime)
    {
        var item = CalcWithAnonymous(a, prime);
        if (item.gcd == 1)
        {
            return PythonMod(item.x, prime);
        }

        throw new ArgumentException("Обратного элемента не существует, т.к. a и p не взаимно просты.");
    }

    #endregion
}