TheAlgorithms/Go · error

no Modular Inverse exists

Error message

no Modular Inverse exists

What it means

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.

Source

Thrown at math/modular/inverse.go:18

// inverse.go
// description: Implementation of Modular Inverse Algorithm
// details:
// A simple implementation of Modular Inverse - [Modular Inverse wiki](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse)
// time complexity: O(log(min(a, b))) where a and b are the two numbers
// space complexity: O(1)
// author(s) [Taj](https://github.com/tjgurwara99)
// see inverse_test.go

package modular

import (
	"errors"

	"github.com/TheAlgorithms/Go/math/gcd"
)

var ErrorInverse = errors.New("no Modular Inverse exists")

// Inverse Modular function
func Inverse(a, m int64) (int64, error) {
	gcd, x, _ := gcd.Extended(a, m)
	if gcd != 1 || m == 0 {
		return 0, ErrorInverse
	}

	return ((m + (x % m)) % m), nil // this is necessary because of Go's use of architecture specific instruction for the % operator.
}

View on GitHub (pinned to 5ba447ec5f)

Solutions

1. 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
2. Handle the m == 0 case explicitly in your caller before invoking Inverse
3. If the inverse must exist mathematically, switch to a modulus coprime to a (e.g., a prime modulus with a not divisible by it)

Example fix

// before
inv, err := modular.Inverse(2, 6) // ErrorInverse: gcd(2,6)=2
// after
if gcd, _ := gcdIterative(2, 6); gcd != 1 {
    return 0, fmt.Errorf("no inverse: gcd(a,m) != 1")
}
inv, err := modular.Inverse(a, m)

g, _, _ := gcd.Extended(a, m)
if m == 0 || g != 1 { return 0, errors.New("no inverse: need m != 0 and gcd(a,m)==1") }

func hasModularInverse(a, m int64) bool {
    if m == 0 { return false }
    g, _, _ := gcd.Extended(a, m)
    return g == 1
}

inv, err := modular.Inverse(a, m)
if err != nil {
    if errors.Is(err, modular.ErrorInverse) {
        // choose a coprime modulus or fail fast with a clear message
    }
    return 0, err
}

When it happens

Trigger: Calling modular.Inverse(a, m) when gcd(a, m) != 1 (e.g., Inverse(2, 6)), or when m == 0 (e.g., Inverse(1, 0)).

Common situations: 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.

Related errors

• integer overflow
• negative Exponent provided
• empty slice provided
• factorization failed
• interval boundaries should be finite numbers

AI-assisted analysis of TheAlgorithms/Go@5ba447ec5f (2026-09-02). Data as JSON: /api/errors/60bd1b494598bb8f. Report an issue: GitHub.