TheAlgorithms/C-Sharp · error · ArithmeticException

is not invertible in Z/ Z.

Error message

{a} is not invertible in Z/{n}Z.

What it means

Thrown by ModularMultiplicativeInverse.Compute when gcd(a, n) != 1, meaning a has no multiplicative inverse modulo n. The method uses ExtendedEuclideanAlgorithm to compute the inverse and checks the resulting GCD before returning it.

Solutions

1. Check gcd(a, n) == 1 before calling Compute (via ExtendedEuclideanAlgorithm) and handle the non-invertible case explicitly.
2. Ensure the modulus n is prime if your algorithm requires all nonzero a to be invertible.
3. Choose a different a (e.g. a different exponent in RSA) that is coprime to n.

Example fix

// before
var inv = ModularMultiplicativeInverse.Compute(a, n);
// after
if (ExtendedEuclideanAlgorithm.Compute(a, n).Gcd == 1)
    var inv = ModularMultiplicativeInverse.Compute(a, n);
else
    throw new InvalidOperationException($"{a} is not invertible mod {n}; pick a coprime value.");

bool invertible = ExtendedEuclideanAlgorithm.Compute(a, n).Gcd == 1;
if (!invertible) throw new ArgumentException($"{a} has no inverse mod {n}");

static bool IsInvertibleMod<T>(T a, T n) where T : System.Numerics.IBinaryNumber<T> =>
    Gcd(a, n) == T.One; // supply your gcd for T

try { inv = ModularMultiplicativeInverse.Compute(a, n); }
catch (ArithmeticException ex) { /* a not invertible: choose another a or fail fast */ }

When it happens

Trigger: Calling ModularMultiplicativeInverse.Compute(a, n) where a and n share a common factor > 1, e.g. Compute(4, 8) (gcd 4) or Compute(6, 9) (gcd 3).

Common situations: RSA-style key computations with non-prime moduli and unlucky exponents; modular division implemented as multiply-by-inverse where the divisor isn't a unit mod n; cryptography or hashing code assuming n is prime when it isn't.

Understand the failure class

Background: UnsupportedOperationException and "is not supported" errors: when a library deliberately refuses a call — this error's family across 30 libraries.

Related errors

• The parameters 'listOfAs' and 'listOfNs' must not be null…
• The value for some n_i is smaller than or equal to 1.
• The value for some a_i is smaller than 0.
• The GCD of n_ = and n_ = equals and thus these values…
• Variance of X must not be zero.

AI-assisted analysis of TheAlgorithms/C-Sharp@96e2905cab (2026-09-13). Data as JSON: /api/errors/2a18361a0d6ea4c0. Report an issue: GitHub.

Appendix: source

Thrown at Algorithms/ModularArithmetic/ModularMultiplicativeInverse.cs:22

/// Modular multiplicative inverse: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse.
/// </summary>
public static class ModularMultiplicativeInverse
{
    /// <summary>
    ///     Computes the modular multiplicative inverse of a in Z/nZ, if there is any (i.e. if a and n are coprime).
    /// </summary>
    /// <param name="a">The number a, of which to compute the multiplicative inverse.</param>
    /// <param name="n">The modulus n.</param>
    /// <returns>The multiplicative inverse of a in Z/nZ, a value in the interval [0, n).</returns>
    /// <exception cref="ArithmeticException">If there exists no multiplicative inverse of a in Z/nZ.</exception>
    public static long Compute(long a, long n)
    {
        var eeaResult = ExtendedEuclideanAlgorithm.Compute(a, n);

        // Check if there is an inverse:
        if (eeaResult.Gcd != 1)
        {
            throw new ArithmeticException($"{a} is not invertible in Z/{n}Z.");
        }

        // Make sure, inverseOfA (i.e. the bezout coefficient of a) is in the interval [0, n).
        var inverseOfA = eeaResult.BezoutA;
        if (inverseOfA < 0)
        {
            inverseOfA += n;
        }

        return inverseOfA;
    }

    /// <summary>
    ///     Computes the modular multiplicative inverse of a in Z/nZ, if there is any (i.e. if a and n are coprime).
    /// </summary>
    /// <param name="a">The number a, of which to compute the multiplicative inverse.</param>
    /// <param name="n">The modulus n.</param>
    /// <returns>The multiplicative inverse of a in Z/nZ, a value in the interval [0, n).</returns>

View on GitHub (pinned to 96e2905cab)