Modular Inverse Calculator

Frequently Asked Questions

What is a modular inverse?

The number x with a·x ≡ 1 (mod m). It is the modular analogue of dividing by a and is central to RSA and other cryptography.

When does it exist?

Only when a and m are coprime, i.e. gcd(a, m) = 1. Otherwise no inverse exists and the calculator says so.

How is it found?

With the extended Euclidean algorithm, which returns integers x, y solving a·x + m·y = gcd(a, m); x mod m is the inverse when the gcd is 1.

Where is this used?

RSA key generation, the Chinese remainder theorem, hashing, and solving linear congruences.

Provided by AllCalculators.io
Free online calculators for everyday. No registration required.

Estimates for informational purposes only.

Important Disclaimer: Estimates for informational purposes only.

This calculator provides estimates for informational purposes only. Results are based on assumptions and may not reflect actual outcomes. Consult qualified professionals in relevant fields before making important decisions based on these results.

JavaScript is required to use the interactive calculator above. The questions and answers below remain readable without JavaScript.

How This Calculator Works

The modular inverse of a (mod m) is the integer a⁻¹ with a × a⁻¹ ≡ 1 (mod m). It exists if and only if gcd(a, m) = 1. The tool runs the extended Euclidean algorithm, which alongside gcd(a, m) returns Bezout coefficients x, y solving ax + my = gcd; when the gcd is 1, that x (reduced mod m) is the inverse. The second mode applies the Chinese Remainder Theorem: given x ≡ r_i (mod m_i) for pairwise-coprime moduli, there is a unique solution mod M = ∏m_i. It is built constructively as x = ∑ r_i M_i (M_i⁻¹ mod m_i), where M_i = M÷m_i - each term hits the right residue for its own modulus and vanishes for the others.

Worked Example

Inverse of 17 (mod 43): the extended Euclidean algorithm gives gcd = 1 with 17 × 38 − 43 × 15 = 1, so 17⁻¹ ≡ 38. Check: 17 × 38 = 646 = 15 × 43 + 1, indeed ≡ 1 (mod 43). CRT example: solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). Here M = 105. The construction yields x = 23, and you can verify 23 mod 3 = 2, 23 mod 5 = 3, 23 mod 7 = 2 - the classic Sun Tzu puzzle from the 3rd century. Every solution differs by a multiple of 105.

Where This Is Used

RSA & cryptography: the private key d is the modular inverse of the public exponent e mod φ(n); CRT speeds up RSA decryption roughly 4×.

Hashing & PRNGs: linear congruential generators and rolling hashes rely on invertible multipliers mod m.

Error-correcting codes and secret sharing reconstruct values from residues using CRT.

Calendar & scheduling math: "every 3rd, 5th and 7th day" alignment problems are CRT in disguise.

Common Mistakes & Edge Cases

No inverse exists when gcd(a, m) ≠ 1 - e.g. 6 has no inverse mod 9. The tool reports the gcd and stops rather than returning a wrong number.

Classical CRT requires the moduli to be pairwise coprime; with shared factors a solution may still exist but needs the generalized form - this tool detects and warns.

Negative inputs are fine: results are normalized into the range 0 … m−1.

The CRT answer is unique only modulo M = ∏m_i; adding any multiple of M gives another valid solution.

m = 1 makes every residue 0 and is degenerate - inverses need m ≥ 2.

Two Routes to the Same Inverse

There are two standard ways to compute a⁻¹ mod m. The extended Euclidean algorithm used here is the workhorse: it runs in O(log m) steps and needs no factorisation of m, only that gcd(a, m) = 1. The alternative is Euler's theorem: when gcd(a, m) = 1, a^φ(m) ≡ 1 (mod m), so a⁻¹ ≡ a^(φ(m)−1). That route is elegant but needs φ(m), which in turn needs the prime factorisation of m - expensive for large m. When m is prime, φ(m) = m−1 and Fermat's little theorem gives the shortcut a⁻¹ ≡ a^(m−2) (mod m), the form used inside many cryptographic libraries because constant-time modular exponentiation resists timing attacks. The Euclidean method, by contrast, is the fastest and the one you would compute by hand.

Related Tools & Limits

This pairs naturally with a GCD/Euclidean calculator and a modular-exponentiation tool (for aⁿ mod m used in RSA encryption itself). Because results use JavaScript doubles, products beyond 2⁵³ lose exact integer precision - fine for textbook moduli but not for 2048-bit cryptographic keys, which require big-integer libraries. The generalized CRT for non-coprime moduli (splitting each modulus into prime powers and merging compatible constraints) and the Euler-totient route to inverses are the natural next topics once the coprime case is solid.

Modular Inverse Calculator

Frequently Asked Questions

Related Math Calculators