{"record":{"id":"da54ff6fe0158cbd","repo":"gchq/CyberChef","slug":"inverse-does-not-exist-because-gcd-a-m-1","errorCode":null,"errorMessage":"Inverse does not exist because gcd(a, m) ≠ 1","messagePattern":"Inverse does not exist because gcd\\(a, m\\) ≠ 1","errorType":"exception","errorClass":"OperationError","httpStatus":null,"severity":"error","filePath":"src/core/operations/ModularInverse.mjs","lineNumber":94,"sourceCode":"            m = inputVal;\n            if (!m) throw new OperationError(\"Modulus (m) must be defined\");\n        } else if (!aParam && !mParam) {\n            // Case 4: value and modulus both missing\n            throw new OperationError(\"Value (a) and Modulus (m) must be defined\");\n        }\n\n        const aBI = parseBigInt(a, \"Value (a)\");\n        const mBI = parseBigInt(m, \"Modulus (m)\");\n\n        if (mBI <= 0n) {\n            throw new OperationError(\"Modulus must be greater than zero\");\n        }\n\n        const aNorm = ((aBI % mBI) + mBI) % mBI;\n        const [g, x] = egcd(aNorm, mBI);\n\n        if (g !== 1n && g !== -1n) {\n            throw new OperationError(\"Inverse does not exist because gcd(a, m) ≠ 1\");\n        }\n\n        let inv = x;\n        if (g === -1n) inv = -inv;\n\n        inv = ((inv % mBI) + mBI) % mBI;\n\n\n        return inv.toString();\n    }\n}\n\nexport default ModularInverse;\n","sourceCodeStart":76,"sourceCodeEnd":108,"githubUrl":"https://github.com/gchq/CyberChef/blob/4290ea753912378913b1f3f54e0fc5720afeda5d/src/core/operations/ModularInverse.mjs#L76-L108","documentation":"Thrown by Modular Inverse when the Extended Euclidean Algorithm yields a gcd g that is neither 1n nor -1n. A modular multiplicative inverse exists only when a and m are coprime (gcd = 1); otherwise no integer x satisfies a*x ≡ 1 (mod m).","triggerScenarios":"run(input, args) where gcd(a mod m, m) is not 1, e.g. a=2 m=4, a=6 m=9, a=0 m=anything, or a sharing a common factor with m. Computed via egcd() over the normalised aNorm.","commonSituations":"Even modulus with even value; value is a multiple of the modulus; value of 0 (gcd(0,m)=m); prime modulus rarely hits this but composite moduli frequently do; testing RSA parameters where p and q are not coprime to the intended modulus.","solutions":["Choose 'a' coprime to 'm' (use a prime modulus, or check gcd first).","If a=0, change it — zero has no inverse.","Pre-compute gcd(a, m) and only call the operation when it equals 1."],"exampleFix":"// before\nchef.bake(\"Modular Inverse\", [\"2\", \"4\"], \"\");  // gcd(2,4)=2 -> error\n// after\nchef.bake(\"Modular Inverse\", [\"3\", \"4\"], \"\");  // gcd(3,4)=1 -> 3","handlingStrategy":"validation","validationCode":"function gcd(a, b) {\n  a = a < 0n ? -a : a; b = b < 0n ? -b : b;\n  while (b) { [a, b] = [b, a % b]; }\n  return a;\n}\nconst aBI = BigInt(a), mBI = BigInt(m);\nif (gcd(((aBI % mBI) + mBI) % mBI, mBI) !== 1n) {\n  // inverse does not exist; pick a different 'a' or 'm'\n}","typeGuard":"const isCoprime = (aBI, mBI) => {\n  let a = ((aBI % mBI) + mBI) % mBI, b = mBI;\n  while (b) { [a, b] = [b, a % b]; }\n  return a === 1n;\n};","tryCatchPattern":"try { chef.bake(\"Modular Inverse\", [a, m]); }\ncatch (e) { if (e.message.startsWith(\"Inverse does not exist\")) findCoprimeA(); else throw e; }","preventionTips":["Use a prime modulus — every non-zero residue is invertible.","Pre-check gcd(a, m) === 1 before calling.","Avoid a === 0, which is never coprime."],"tags":["crypto","modular-arithmetic","number-theory"],"backgroundTag":null,"analyzedSha":"4290ea753912378913b1f3f54e0fc5720afeda5d","analyzedAt":"2026-08-13T06:05:50.210Z","schemaVersion":2},"datasetVersion":"2026-08-13T09:17:06.757Z"}