What is a modular inverse?

Given an integer \(a\) and a modulus \(m > 1\), a modular multiplicative inverse of \(a\) modulo \(m\) is an integer \(x\) such that \[ a x \equiv 1 \pmod m. \]

Intuitively, \(x\) plays the role of a reciprocal of \(a\) in modular arithmetic: multiplying by \(x\) “undoes” the effect of multiplying by \(a\), but only up to congruence modulo \(m\).

Existence and uniqueness

• A modular inverse exists if and only if \(\gcd(a, m) = 1\) (that is, \(a\) and \(m\) are coprime).
• If an inverse exists, it is unique modulo \(m\). All solutions differ by a multiple of \(m\).
• If \(\gcd(a, m) > 1\), then no modular inverse exists.

Algorithm used by this calculator

This calculator uses the extended Euclidean algorithm, a classic number-theoretic method that not only computes \(\gcd(a, m)\) but also finds integers \(x\) and \(y\) such that \[ a x + m y = \gcd(a, m). \]

When \(\gcd(a, m) = 1\), the coefficient \(x\) is precisely a modular inverse of \(a\) modulo \(m\). We then reduce \(x\) to the standard range \(0 \le x \le m-1\).

Worked example

Consider \(a = 17\) and \(m = 43\).

1. They are already reduced, so \(a' = 17\), \(m = 43\).
2. Compute \(\gcd(17, 43)\) with the extended Euclidean algorithm. We find \(\gcd(17, 43) = 1\).
3. One of the Bézout representations is \[ 17 \cdot 38 + 43 \cdot (-15) = 1. \] Therefore \(x = 38\) is a modular inverse of \(17\) modulo \(43\).
4. Check: \[ 17 \cdot 38 = 646,\quad 646 \bmod 43 = 1. \]

So the calculator will display \(x = 38\) as the modular inverse.

Typical applications

• Cryptography — RSA key generation, Diffie–Hellman, ECDSA and other public-key schemes.
• Chinese remainder theorem — combining congruences with different moduli.
• Solving linear congruences — equations of the form \(a x \equiv b \pmod m\).
• Modular linear algebra — inverting matrices modulo a prime.
• Coding theory and algorithms — operations in finite fields and residue rings.

Frequently asked questions

How do I solve \(a x \equiv b \pmod m\) using the modular inverse?

First, compute the modular inverse \(a^{-1}\) of \(a\) modulo \(m\) (if it exists). Then multiply both sides of the congruence by \(a^{-1}\): \[ x \equiv a^{-1} b \pmod m. \] This calculator gives you \(a^{-1}\); you can then multiply by \(b\) and reduce modulo \(m\).

What if \(\gcd(a, m) \neq 1\)?

If \(\gcd(a, m) > 1\), then \(a\) does not have a modular inverse modulo \(m\). In that case, the calculator clearly states that no inverse exists. For a congruence \(a x \equiv b \pmod m\), solutions may still exist, but they require a slightly different analysis (dividing everything by \(\gcd(a, m)\) and reducing the modulus).

Can I use negative values for \(a\)?

Yes. The calculator internally replaces \(a\) with \(a' = a \bmod m\), so negative values are reduced to an equivalent representative in \(\{0, 1, \dots, m-1\}\) before applying the algorithm.

Are very large cryptographic moduli supported?

This implementation uses standard JavaScript integers and is numerically safe up to \(|a|, |m| \le 9{,}007{,}199{,}254{,}740{,}991\) (the maximum safe integer in JavaScript). For industrial-grade cryptographic key sizes (for example 2048-bit RSA), you should rely on specialised big-integer libraries or computer algebra systems.