gchq/CyberChef · error · OperationError

Inverse does not exist because gcd(a, m) ≠ 1

Error message

Inverse does not exist because gcd(a, m) ≠ 1

What it means

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).

Source

Thrown at src/core/operations/ModularInverse.mjs:94

            m = inputVal;
            if (!m) throw new OperationError("Modulus (m) must be defined");
        } else if (!aParam && !mParam) {
            // Case 4: value and modulus both missing
            throw new OperationError("Value (a) and Modulus (m) must be defined");
        }

        const aBI = parseBigInt(a, "Value (a)");
        const mBI = parseBigInt(m, "Modulus (m)");

        if (mBI <= 0n) {
            throw new OperationError("Modulus must be greater than zero");
        }

        const aNorm = ((aBI % mBI) + mBI) % mBI;
        const [g, x] = egcd(aNorm, mBI);

        if (g !== 1n && g !== -1n) {
            throw new OperationError("Inverse does not exist because gcd(a, m) ≠ 1");
        }

        let inv = x;
        if (g === -1n) inv = -inv;

        inv = ((inv % mBI) + mBI) % mBI;


        return inv.toString();
    }
}

export default ModularInverse;

View on GitHub (pinned to 4290ea7539)

Solutions

1. Choose 'a' coprime to 'm' (use a prime modulus, or check gcd first).
2. If a=0, change it — zero has no inverse.
3. Pre-compute gcd(a, m) and only call the operation when it equals 1.

Example fix

// before
chef.bake("Modular Inverse", ["2", "4"], "");  // gcd(2,4)=2 -> error
// after
chef.bake("Modular Inverse", ["3", "4"], "");  // gcd(3,4)=1 -> 3

function gcd(a, b) {
  a = a < 0n ? -a : a; b = b < 0n ? -b : b;
  while (b) { [a, b] = [b, a % b]; }
  return a;
}
const aBI = BigInt(a), mBI = BigInt(m);
if (gcd(((aBI % mBI) + mBI) % mBI, mBI) !== 1n) {
  // inverse does not exist; pick a different 'a' or 'm'
}

const isCoprime = (aBI, mBI) => {
  let a = ((aBI % mBI) + mBI) % mBI, b = mBI;
  while (b) { [a, b] = [b, a % b]; }
  return a === 1n;
};

try { chef.bake("Modular Inverse", [a, m]); }
catch (e) { if (e.message.startsWith("Inverse does not exist")) findCoprimeA(); else throw e; }

When it happens

Trigger: 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.

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

Related errors

• Modulus must be greater than zero
• Value (a) must be defined
• Modulus (m) must be defined
• Value (a) and Modulus (m) must be defined
• Modulus must be greater than zero

AI-assisted analysis of gchq/CyberChef@4290ea7539 (2026-08-13). Data as JSON: /api/errors/da54ff6fe0158cbd. Report an issue: GitHub.