Modular inverse calculator

This modular inverse calculator finds the modular multiplicative inverse of an integer \(a\) modulo \(m\). In other words, it finds an integer \(x\) such that \(a x \equiv 1 \pmod m\), or tells you when no such inverse exists.

The tool is built for students, engineers and cryptography practitioners who need a reliable, step-by-step implementation of the extended Euclidean algorithm.

Any non-zero integer. The calculator will automatically reduce it modulo \(m\).

Positive integer > 1. For cryptography, \(m\) is often a large prime or product of primes.

Quick examples

Click an example to auto-fill the fields and see a typical modular inverse computation.

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

Extended Euclidean algorithm (high-level outline)

  1. Reduce the input \(a\) modulo \(m\): set \(a' = a \bmod m\).
  2. Initialize \(r_0 = a'\), \(r_1 = m\), \(s_0 = 1\), \(s_1 = 0\), \(t_0 = 0\), \(t_1 = 1\).
  3. Repeat until \(r_k = 0\):
    • Compute the quotient \(q_k = \lfloor r_{k-1} / r_k \rfloor\).
    • Update \(r_{k+1} = r_{k-1} - q_k r_k\).
    • Update \(s_{k+1} = s_{k-1} - q_k s_k\), \(t_{k+1} = t_{k-1} - q_k t_k\).
  4. When the loop ends, the last non-zero remainder is \(\gcd(a', m)\), and the corresponding \(s\) is the inverse.

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.