{"record":{"id":"60bd1b494598bb8f","repo":"TheAlgorithms/Go","slug":"no-modular-inverse-exists","errorCode":null,"errorMessage":"no Modular Inverse exists","messagePattern":"no Modular Inverse exists","errorType":"validation","errorClass":null,"httpStatus":null,"severity":"error","filePath":"math/modular/inverse.go","lineNumber":18,"sourceCode":"// inverse.go\n// description: Implementation of Modular Inverse Algorithm\n// details:\n// A simple implementation of Modular Inverse - [Modular Inverse wiki](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse)\n// time complexity: O(log(min(a, b))) where a and b are the two numbers\n// space complexity: O(1)\n// author(s) [Taj](https://github.com/tjgurwara99)\n// see inverse_test.go\n\npackage modular\n\nimport (\n\t\"errors\"\n\n\t\"github.com/TheAlgorithms/Go/math/gcd\"\n)\n\nvar ErrorInverse = errors.New(\"no Modular Inverse exists\")\n\n// Inverse Modular function\nfunc Inverse(a, m int64) (int64, error) {\n\tgcd, x, _ := gcd.Extended(a, m)\n\tif gcd != 1 || m == 0 {\n\t\treturn 0, ErrorInverse\n\t}\n\n\treturn ((m + (x % m)) % m), nil // this is necessary because of Go's use of architecture specific instruction for the % operator.\n}\n","sourceCodeStart":1,"sourceCodeEnd":29,"githubUrl":"https://github.com/TheAlgorithms/Go/blob/5ba447ec5ff3d1213de65b92e726ee74c5d5cc19/math/modular/inverse.go#L1-L29","documentation":"ErrorInverse is returned by modular.Inverse when no modular multiplicative inverse of a modulo m exists (math/modular/inverse.go:18). The inverse exists only when gcd(a, m) == 1 and m != 0; the function computes the extended GCD and returns 0 with this error otherwise.","triggerScenarios":"Calling modular.Inverse(a, m) when gcd(a, m) != 1 (e.g., Inverse(2, 6)), or when m == 0 (e.g., Inverse(1, 0)).","commonSituations":"Passing a modulus that shares factors with a (non-prime or non-coprime modulus); accidentally passing 0 as the modulus because it was unset/zero-valued; using an even a with an even modulus.","solutions":["Ensure a and m are coprime before calling: check gcd.Extended(a, m).GCD == 1, or reduce a modulo m and/or use a prime modulus","Handle the m == 0 case explicitly in your caller before invoking Inverse","If the inverse must exist mathematically, switch to a modulus coprime to a (e.g., a prime modulus with a not divisible by it)"],"exampleFix":"// before\ninv, err := modular.Inverse(2, 6) // ErrorInverse: gcd(2,6)=2\n// after\nif gcd, _ := gcdIterative(2, 6); gcd != 1 {\n    return 0, fmt.Errorf(\"no inverse: gcd(a,m) != 1\")\n}\ninv, err := modular.Inverse(a, m)","handlingStrategy":"validation","validationCode":"g, _, _ := gcd.Extended(a, m)\nif m == 0 || g != 1 { return 0, errors.New(\"no inverse: need m != 0 and gcd(a,m)==1\") }","typeGuard":"func hasModularInverse(a, m int64) bool {\n    if m == 0 { return false }\n    g, _, _ := gcd.Extended(a, m)\n    return g == 1\n}","tryCatchPattern":"inv, err := modular.Inverse(a, m)\nif err != nil {\n    if errors.Is(err, modular.ErrorInverse) {\n        // choose a coprime modulus or fail fast with a clear message\n    }\n    return 0, err\n}","preventionTips":["Always verify gcd(a, m) == 1 before needing an inverse","Never pass an unset (zero) modulus; validate m > 0 first","Prefer prime moduli so inverses exist for all non-multiples","Check errors.Is(err, modular.ErrorInverse) rather than ignoring err"],"tags":["go","math","modular-arithmetic","modular-inverse"],"backgroundTag":"no-modular-inverse","analyzedSha":"5ba447ec5ff3d1213de65b92e726ee74c5d5cc19","analyzedAt":"2026-09-02T21:54:30.227Z","contentChangedAt":null,"schemaVersion":2},"datasetVersion":"2026-09-10T02:17:09.455Z"}