{"record":{"id":"2a18361a0d6ea4c0","repo":"TheAlgorithms/C-Sharp","slug":"a-is-not-invertible-in-z-n-z","errorCode":null,"errorMessage":"{a} is not invertible in Z/{n}Z.","messagePattern":"(.+?) is not invertible in Z/(.+?)Z\\.","errorType":"exception","errorClass":"ArithmeticException","httpStatus":null,"severity":"error","filePath":"Algorithms/ModularArithmetic/ModularMultiplicativeInverse.cs","lineNumber":22,"sourceCode":"/// Modular multiplicative inverse: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse.\n/// </summary>\npublic static class ModularMultiplicativeInverse\n{\n    /// <summary>\n    ///     Computes the modular multiplicative inverse of a in Z/nZ, if there is any (i.e. if a and n are coprime).\n    /// </summary>\n    /// <param name=\"a\">The number a, of which to compute the multiplicative inverse.</param>\n    /// <param name=\"n\">The modulus n.</param>\n    /// <returns>The multiplicative inverse of a in Z/nZ, a value in the interval [0, n).</returns>\n    /// <exception cref=\"ArithmeticException\">If there exists no multiplicative inverse of a in Z/nZ.</exception>\n    public static long Compute(long a, long n)\n    {\n        var eeaResult = ExtendedEuclideanAlgorithm.Compute(a, n);\n\n        // Check if there is an inverse:\n        if (eeaResult.Gcd != 1)\n        {\n            throw new ArithmeticException($\"{a} is not invertible in Z/{n}Z.\");\n        }\n\n        // Make sure, inverseOfA (i.e. the bezout coefficient of a) is in the interval [0, n).\n        var inverseOfA = eeaResult.BezoutA;\n        if (inverseOfA < 0)\n        {\n            inverseOfA += n;\n        }\n\n        return inverseOfA;\n    }\n\n    /// <summary>\n    ///     Computes the modular multiplicative inverse of a in Z/nZ, if there is any (i.e. if a and n are coprime).\n    /// </summary>\n    /// <param name=\"a\">The number a, of which to compute the multiplicative inverse.</param>\n    /// <param name=\"n\">The modulus n.</param>\n    /// <returns>The multiplicative inverse of a in Z/nZ, a value in the interval [0, n).</returns>","sourceCodeStart":4,"sourceCodeEnd":40,"githubUrl":"https://github.com/TheAlgorithms/C-Sharp/blob/96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c/Algorithms/ModularArithmetic/ModularMultiplicativeInverse.cs#L4-L40","documentation":"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.","triggerScenarios":"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).","commonSituations":"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.","solutions":["Check gcd(a, n) == 1 before calling Compute (via ExtendedEuclideanAlgorithm) and handle the non-invertible case explicitly.","Ensure the modulus n is prime if your algorithm requires all nonzero a to be invertible.","Choose a different a (e.g. a different exponent in RSA) that is coprime to n."],"exampleFix":"// before\nvar inv = ModularMultiplicativeInverse.Compute(a, n);\n// after\nif (ExtendedEuclideanAlgorithm.Compute(a, n).Gcd == 1)\n    var inv = ModularMultiplicativeInverse.Compute(a, n);\nelse\n    throw new InvalidOperationException($\"{a} is not invertible mod {n}; pick a coprime value.\");","handlingStrategy":"validation","validationCode":"bool invertible = ExtendedEuclideanAlgorithm.Compute(a, n).Gcd == 1;\nif (!invertible) throw new ArgumentException($\"{a} has no inverse mod {n}\");","typeGuard":"static bool IsInvertibleMod<T>(T a, T n) where T : System.Numerics.IBinaryNumber<T> =>\n    Gcd(a, n) == T.One; // supply your gcd for T","tryCatchPattern":"try { inv = ModularMultiplicativeInverse.Compute(a, n); }\ncatch (ArithmeticException ex) { /* a not invertible: choose another a or fail fast */ }","preventionTips":["Use prime moduli when all nonzero elements must be invertible.","Guard a != 0 for n > 1.","In RSA-style code, assert gcd(e, phi) == 1 when picking exponents."],"tags":["csharp","math","modular-arithmetic","gcd"],"backgroundTag":"unsupported-operation","analyzedSha":"96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c","analyzedAt":"2026-09-13T17:04:01.438Z","contentChangedAt":"2026-09-13T17:04:01.438Z","schemaVersion":2},"datasetVersion":"2026-09-16T04:17:20.429Z"}