Modular Inverse Calculator: Three Routes to a⁻¹ mod n
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
A modular inverse calculator answers a question that looks like division but isn’t: which whole number x satisfies 7x ≡ 1 (mod 26)? The answer is 15, because 7 × 15 = 105 = 4 × 26 + 1. No fractions appear anywhere. That single number is what lets you divide by 7 in modular arithmetic, and it’s the reason RSA key generation works at all.
Three methods find it. One is what every library uses, one is what cryptographic code uses when timing attacks matter, and one is what you should never use but everyone tries first. Below: the condition that decides whether an inverse exists at all, the three routes measured against each other, two hand methods worked through in full, and the check that catches every arithmetic slip.
gcd(a, n) = 1, or There Is No Inverse
Most numbers have no modular inverse, and the test takes one line. An inverse of a modulo n exists exactly when a and n share no factor beyond 1 — when gcd(a, n) = 1. That’s not a convention; it falls out of the arithmetic. Every multiple of 6 is also a multiple of 3, so modulo 9 the products 6 × 1, 6 × 2, 6 × 3, … only ever land on 6, 3, or 0. The value 1 is never in that list, so 6 has no inverse mod 9. Try it in the calculator: gcd(6, 9) = 3 and the verdict card names the blocking factor.
Flip it around and the same logic tells you how many invertible numbers a modulus has: exactly φ(n) of them, Euler’s totient. Modulo 26 that’s 12 — barely half the residues, which is why the classical affine cipher only permits twelve multiplier keys. Modulo a prime, φ(p) = p − 1, so every nonzero residue is invertible and the existence question stops mattering. That difference is worth checking before you start: the greatest common factor calculator settles coprimality in a second, and the Euler phi calculator counts the invertible class for any modulus.
| Modulus n | Invertible φ(n) | Share | What blocks the rest |
|---|---|---|---|
| 11 (prime) | 10 | 91% | only 0 |
| 26 = 2 × 13 | 12 | 46% | every even number, plus 13 |
| 3120 = 2⁴ × 3 × 5 × 13 | 768 | 25% | anything even, or divisible by 3, 5, or 13 |
| 10⁹ + 7 (prime) | 10⁹ + 6 | ~100% | only 0 |
Read the 3120 row twice, because it’s the RSA case. Three quarters of all candidate exponents are unusable against that modulus — not a rare edge case, the common one. Key generation picks e and then checks gcd(e, φ(n)) = 1 for exactly this reason.
Extended Euclid, Fermat, or a Search: What a Modular Inverse Calculator Runs
All three routes below return the identical number. They differ in what they need to know beforehand and in how much work they do — and the gap is not subtle. Take 17⁻¹ mod 3120, the textbook RSA key with p = 61 and q = 53, where the answer is d = 2753.
| Route | Cost for 17⁻¹ mod 3120 | Prerequisite | Use it when |
|---|---|---|---|
| Extended Euclid | 4 divisions | none | always, unless timing leaks matter |
| Fermat / Euler power | 17 modular multiplications | φ(3120) = 768, so n factored | prime modulus, or constant-time code |
| Brute-force scan | 2,753 trials | none | never, past n ≈ 10,000 |
Four divisions against 2,753 multiplications is a 700-fold gap on a four-digit modulus, and it widens without limit: Euclid’s step count grows with the number of digits in n while the scan grows with n itself. Push the modulus to 10⁹ + 7 and Euclid averages about 17 divisions — the theoretical ceiling is 45 — while the average scan needs half a billion multiplications.
The Fermat row hides the real trap. Raising a to the power φ(n) − 1 is genuinely elegant — 17 modular multiplications is competitive — but you cannot write down φ(3120) = 768 without first factoring 3120 into 2⁴ × 3 × 5 × 13. For a 2048-bit RSA modulus that factorisation is the thing the entire security model assumes nobody can do. Set the modulus to something large in the calculator, switch to the Euler method, and the panel refuses the job rather than pretend. Extended Euclid never asks the question. That asymmetry, not raw speed, is why every crypto library computes inverses with Euclid.
The Table That Produces d = 2753
Extended Euclid runs the ordinary gcd algorithm while carrying two extra columns. Each row tracks how the current remainder can be written as s × n + t × a. When the remainder hits 1, the t in that row is the inverse. Here it is on a = 17, n = 3120:
| Division | Remainder r | s (× 3120) | t (× 17) |
|---|---|---|---|
| start | 3120 | 1 | 0 |
| start | 17 | 0 | 1 |
| 3120 = 183 × 17 + 9 | 9 | 1 | −183 |
| 17 = 1 × 9 + 8 | 8 | −1 | 184 |
| 9 = 1 × 8 + 1 | 1 | 2 | −367 |
The final row says 2 × 3120 + (−367) × 17 = 1, and you can check that by hand: 6240 − 6239 = 1. Reduce it modulo 3120 and the 3120 term vanishes, leaving −367 × 17 ≡ 1. So −367 is an inverse of 17. Add the modulus once to bring it into range: −367 + 3120 = 2753. That’s the RSA private exponent, and 17 × 2753 = 46,801 = 15 × 3120 + 1 confirms it.
Two details trip people up in that table. The s column is never needed — it exists only to make the row arithmetic uniform, and you can drop it entirely if you only want the inverse. And the t values grow before they resolve (0, 1, −183, 184, −367), which looks like a mistake the first time. It isn’t; the coefficients of a Bézout identity are genuinely larger than the remainders they describe. If you want the plain remainders without the coefficient bookkeeping, the modulo calculator handles those directly.
Back-Substitution: The Same Identity, Built Backwards
Exams often teach the other hand method, and students who learned one panic when they see the other. They produce identical output. Back-substitution runs the plain Euclidean division chain first, then unwinds it. Take 7⁻¹ mod 26:
26 = 3 × 7 + 5
7 = 1 × 5 + 2
5 = 2 × 2 + 1 ← remainder 1, stop
Now walk back up, replacing each remainder with the expression that produced it. Start from the last line, 1 = 5 − 2 × 2. Substitute 2 = 7 − 1 × 5 to get 1 = 5 − 2(7 − 5) = 3 × 5 − 2 × 7. Substitute 5 = 26 − 3 × 7 to get 1 = 3(26 − 3 × 7) − 2 × 7 = 3 × 26 − 11 × 7.
There’s the identity: 3 × 26 − 11 × 7 = 78 − 77 = 1, so −11 is an inverse of 7, and −11 + 26 = 15. The tabular method on the same input produces s = 3 and t = −11 in its final row — the same two coefficients, because the Bézout identity for a coprime pair is unique up to adding multiples of the modulus. Pick whichever method your grader expects; the calculator traces the tabular one because it needs no second pass and never grows a substitution stack.
What 3 ÷ 7 Means Modulo 26
Modular arithmetic has no fractions, so division is defined as multiplication by an inverse: b ÷ a becomes b × a⁻¹. Solving 7x ≡ 3 (mod 26) means multiplying both sides by 15, giving x ≡ 45 ≡ 19. Check: 7 × 19 = 133 = 5 × 26 + 3. Enter a = 7, n = 26, b = 3 in the calculator and the congruence panel walks that through.
Competitive programmers lean on this constantly. Answers “modulo 10⁹ + 7” often involve dividing by a factorial, and since 10⁹ + 7 is prime every nonzero value has an inverse, so a fraction like 1/6 becomes 6⁻¹ mod (10⁹ + 7) = 166,666,668. Combine that with the modular exponentiation calculator and binomial coefficients stay exact with no big-integer arithmetic anywhere.
The case nearly every tool botches is a non-coprime one that’s still solvable. Consider 6x ≡ 3 (mod 9). No inverse of 6 exists, yet x = 2, 5, and 8 all work. The rule: a·x ≡ b (mod n) has solutions exactly when gcd(a, n) divides b, and then it has gcd(a, n) of them. Here gcd = 3 divides 3, so divide the congruence through by 3 to get 2x ≡ 1 (mod 3), solve that (x ≡ 2), and lift it back in steps of 9 ÷ 3 = 3. Most inverse calculators stop at “no inverse” and leave you stuck; this one solves the reduced congruence instead. If you need to check which divisions are clean in the first place, the divisibility calculator is quicker than factoring by hand.
One Multiplication Catches Every Mistake
Every modular inverse is self-checking. Multiply a by your answer, reduce mod n, and you must get 1 — no exceptions, no rounding, no judgement call. That one line catches all four common slips:
- Inverting against the wrong modulus. The classic RSA error: d is e⁻¹ mod φ(n), not e⁻¹ mod n. With p = 61 and q = 53, encrypting the message 65 gives 65¹⁷ mod 3233 = 2790. The correct key, 17⁻¹ mod 3120 = 2753, turns that back into 65. Invert 17 against 3233 instead and you get 2092 — a perfectly valid inverse of 17 that decrypts 2790 to 2699. Nothing errors out; the plaintext is simply wrong. The published PKCS #1 specification is explicit that d inverts e modulo λ(n).
- Leaving the coefficient negative. Euclid hands back −367 or −11. Both are correct residues, but a language whose % truncates toward zero — C, Java, JavaScript, Go — will keep the sign and every downstream comparison silently breaks. Add n once.
- Reaching for a decimal. 7⁻¹ mod 26 is 15, not 0.142857. The modular inverse is always a whole number in 1 … n − 1, and any answer with a decimal point is a sign you computed 1/a instead.
- Skipping the gcd check. Feeding a non-coprime pair to a naive implementation doesn’t always error out — some return the Bézout coefficient anyway, which is a real number that is not an inverse. Verify with the multiplication and it dies immediately: 6 × 5 mod 9 = 3, not 1.
Worth internalising the shape of the whole thing: the extended Euclidean algorithm computes a gcd and an inverse in the same pass, so the existence test is free — the standard formulation returns both. You never need to test coprimality first and then invert. Run one algorithm; if the final remainder is 1 you have your answer, and if it isn’t, that remainder is precisely the factor standing in the way. For the plain remainder arithmetic underneath all of this, the remainder calculator is the simpler starting point.
