{"record":{"id":"5ff96f75db12cd06","repo":"TheAlgorithms/Python","slug":"mod-inverse-of-a-r-and-m-r-does-not-exist","errorCode":null,"errorMessage":"mod inverse of {a!r} and {m!r} does not exist","messagePattern":"mod inverse of (.+?) and (.+?) does not exist","errorType":"exception","errorClass":"ValueError","httpStatus":null,"severity":"error","filePath":"ciphers/cryptomath_module.py","lineNumber":7,"sourceCode":"from maths.greatest_common_divisor import gcd_by_iterative\n\n\ndef find_mod_inverse(a: int, m: int) -> int:\n    if gcd_by_iterative(a, m) != 1:\n        msg = f\"mod inverse of {a!r} and {m!r} does not exist\"\n        raise ValueError(msg)\n    u1, u2, u3 = 1, 0, a\n    v1, v2, v3 = 0, 1, m\n    while v3 != 0:\n        q = u3 // v3\n        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3\n    return u1 % m\n","sourceCodeStart":1,"sourceCodeEnd":14,"githubUrl":"https://github.com/TheAlgorithms/Python/blob/f5988cc09713315817df6a7e327e258013a94440/ciphers/cryptomath_module.py#L1-L14","documentation":"Raised by find_mod_inverse(a, m) in ciphers/cryptomath_module.py when gcd(a, m) != 1, i.e. a has no modular inverse modulo m. This is a mathematical precondition failure, not a bug: the extended Euclidean algorithm only yields an inverse for coprime operands.","triggerScenarios":"find_mod_inverse(4, 8) (gcd is 4); RSA key generation where e shares a factor with phi(n); affine cipher setup with a not coprime to 26.","commonSituations":"RSA implementations picking an exponent e that is not coprime to (p-1)(q-1); hill/affine cipher key selection where the multiplier must be invertible mod alphabet size; reusing parameters after changing modulus size.","solutions":["Choose a value of a coprime to m (check gcd(a, m) == 1 first)","For RSA: pick a different exponent e, commonly 65537, or different primes p and q","For affine ciphers mod 26: restrict a to {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}"],"exampleFix":"# before\ninv = find_mod_inverse(e, phi)  # may raise if gcd(e, phi) != 1\n\n# after\nfrom maths.greatest_common_divisor import gcd_by_iterative as gcd\nif gcd(e, phi) != 1:\n    raise SystemExit(\"pick e coprime to phi\")\ninv = find_mod_inverse(e, phi)","handlingStrategy":"validation","validationCode":"from maths.greatest_common_divisor import gcd_by_iterative as gcd\nassert gcd(a, m) == 1, f\"{a} has no inverse mod {m}\"","typeGuard":null,"tryCatchPattern":"try:\n    inv = find_mod_inverse(a, m)\nexcept ValueError:\n    # no inverse exists; pick different parameters\n    raise","preventionTips":["Always pre-check gcd(a, m) == 1 before find_mod_inverse","In RSA, validate e against phi(n) before computing d","Restrict affine-cipher multipliers to values coprime with the alphabet size"],"tags":["modular-arithmetic","rsa","math","validation"],"backgroundTag":null,"analyzedSha":"f5988cc09713315817df6a7e327e258013a94440","analyzedAt":"2026-08-14T17:30:07.041Z","schemaVersion":2},"datasetVersion":"2026-08-15T17:31:12.345Z"}