The number that undoes a, or the reason there isn’t one.
The number that undoes a
Or the reason there isn’t one.
3⁻¹ mod 26
9
Because 3 × 9 leaves a remainder of 1 when divided by 26 — which is what an inverse means here.
Inverse
9
the only one below 26
gcd(a, n)
1
1, which is what makes it exist
Bézout identity
(3)·(9) + (26)·(-1) = 1
where the inverse comes from
Check
3 × 9 ≡ 1
3 × 9 = 27 = 1 × 26 + 1
The Euclidean algorithm, which produced it
Each division step of the Euclidean algorithm with its quotient and remainder
Step
Division
Quotient
Remainder
1
3 ÷ 26
0
3
2
26 ÷ 3
8
2
3
3 ÷ 2
1
1
4
2 ÷ 1
2
0
The remainders shrink to 1, and tracking the coefficients back up the table produces (3)·(9) + (26)·(-1) = 1. Reducing the coefficient on 3 modulo 26 gives 9— the inverse is a by-product of the gcd, not a separate search.
Found by extended Euclid rather than by trying every candidate, so a nine-digit modulus takes the same instant as a two-digit one.
What this tool shows
There is no dividing by 3 modulo 26 — you multiply by 9 instead, because 3 × 9 = 27, which leaves 1. That 9 is the modular inverse, and it exists only because 3 and 26 share no factor.
The multiplicative inverse of a modulo n
Every step of the Euclidean algorithm that found it
The Bézout identity ax + ny = 1
The check, a × a⁻¹ ≡ 1
Why no inverse exists when a and n share a factor
Which factor they share
Division’s replacement Multiplied back to 1 The RSA key relation Every Euclidean step shown
Exact; found by extended Euclid, not by searching.
Updated 7 September 2026 · Works in any browser, no installation
It is the number that multiplies a to 1, modulo n. For 3 modulo 26 that is 9, since 3 × 9 = 27 = 26 + 1. It exists exactly when a and n share no factor, and the extended Euclidean algorithm finds it in a handful of steps rather than by trying every candidate.
At a glance
Formula shown
a\u207b\u00b9 mod n is the x with ax \u2261 1 (mod n). It exists exactly when gcd(a, n) = 1. The extended Euclidean algorithm produces integers x and y with ax + ny = gcd(a, n); when that gcd is 1, reducing x modulo n gives the inverse.
Scenario support
Decrypting an affine cipher; deriving an RSA private exponent from a public one; dividing inside a modular calculation, where ordinary division does not exist.
Educational estimate
Planning support from the values you enter — not professional advice.
What an inverse is for
Modular arithmetic has addition, subtraction and multiplication. It does not have division. There is no meaningful “divide by 3” modulo 26.
The inverse is the replacement. Instead of dividing by 3 you multiply by 9, and because 3 × 9 ≡ 1, the two operations cancel exactly as division would.
Everything that needs to undo a multiplication uses this: decrypting a cipher that multiplied, solving a linear congruence, or recovering a plaintext from a ciphertext. The inverse is what makes the operation reversible.
When there isn’t one
13 has no inverse modulo 26. Neither does 4 modulo 10. This is not a limitation of the algorithm — the number genuinely does not exist.
The reason is short. 13 and 26 share the factor 13, so every multiple of 13 is also a multiple of 13 — 0, 13, 0, 13 as you go round. The value 1 is never among them, so nothing multiplies 13 to 1.
The general rule: an inverse exists exactly when gcd(a, n) = 1. When the gcd is anything larger, the multiples of a land only on multiples of that gcd, and 1 is not one of them.
So the page treats a refusal as a result. It names the shared factor and says why the multiples can never reach 1, which is the actual answer to the question that was asked.
Where the number comes from
You could find an inverse by trying every value below the modulus. For 26 that is 26 attempts; for a 600-digit RSA modulus it is more attempts than there is time.
The extended Euclidean algorithm gets there directly. Running Euclid on a and n produces their gcd, and tracking the coefficients back up the divisions produces integers x and y with ax + ny = gcd(a, n).
When that gcd is 1, read the identity modulo n: the ny term vanishes, leaving ax ≡ 1. So x IS the inverse, reduced into range. For 3 and 26 the identity is 3×9 + 26×(−1) = 1, and 9 is the answer.
The table on this page is that computation, step by step. The number of steps grows with the number of DIGITS, not the size of the modulus, which is why it stays instant at any scale.
Choosing a cipher key
The affine cipher encrypts a letter as (a·x + b) mod 26. Decrypting means undoing the multiplication, which needs a’s inverse modulo 26.
That is why the multiplier cannot be chosen freely. 26 = 2 × 13, so any even multiplier or 13 itself has no inverse, and the cipher would be undecryptable — different letters would encrypt to the same character.
Twelve of the twenty-six possible multipliers work: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 and 25. That count is φ(26), and it is exactly the number of values with an inverse.
The RSA key relation
RSA’s two exponents are modular inverses of each other. Choose e, compute d with ed ≡ 1 (mod φ(n)), and encryption followed by decryption returns the message.
In the textbook example, n = 3233 with φ(n) = 3120, and e = 17. The private exponent is 17⁻¹ mod 3120 = 2753 — one run of the extended Euclidean algorithm.
The security is not in that step, which is fast and public. It is in φ(n): computing it needs the factors of n, and factoring a large n is the hard problem RSA rests on. Given the factors, the private key falls out in milliseconds.
How many numbers have one
Modulo n, the values with an inverse are exactly those coprime to n. Counting them is Euler’s totient function, φ(n).
For a prime p every value from 1 to p−1 is coprime to it, so φ(p) = p−1 and every non-zero value is invertible. That is what makes prime moduli so convenient: division always works.
For a composite modulus the count drops. φ(26) = 12, so fewer than half the residues have an inverse. φ(12) = 4 — only 1, 5, 7 and 11.
This is also why RSA moduli are products of exactly two primes: φ(pq) = (p−1)(q−1) is easy to compute if you know p and q, and effectively impossible if you do not.
Sources and methodology
The algorithm and the standard that uses it are both published — these are the references.
Method. The inverse comes out of the extended Euclidean algorithm rather than a search, so a nine-digit modulus costs the same as a two-digit one. The step table is the algorithm’s own trace. When the gcd is not 1 the page factorises it and names the shared prime, because "no inverse" without the reason is not an answer. The suite compares every result against an exhaustive search over all pairs below sixty, in both directions — a returned inverse must match, and a refusal must correspond to a search that genuinely found nothing. That engine is verified on every change against 69 hand-written assertions, including that every inverse multiplies back to exactly 1, and that the results agree with an exhaustive search on all 3,422 pairs below sixty — refusals included. The count and the per-case breakdown are published on the formula verification page.
Related calculators
Where this goes next:
ModuloAll three conventions at once, because −7 mod 3 is −1 in JavaScript and 2 in Python and a page that gives only one of those is wrong for half its readers.
Modular Exponentiation7^128 mod 13 without ever building the 109-digit power. Square-and-multiply is shown one exponent bit at a time, with the count of multiplications it saved.
CoprimeSet coprimality and pairwise coprimality are different conditions: 6, 10 and 15 have gcd 1 and not one coprime pair. Both are reported, with the offending pairs named.
GCFThe greatest common factor of two to six numbers with all three routes shown — the shared primes to their lower powers, Euclid line by line, and the full factor lists when they are short enough to be honest.
Prime NumberWhether a number is prime, with a divisor named when it is not and the size of the search stated when it is. Deterministic, not probabilistic.
Chinese Remainder TheoremSolves a system of congruences including the moduli that are not coprime, which most tools refuse — with the merge shown one congruence at a time.
Published the modular inverse page treating a refusal as an answer: when no inverse exists the page names the shared factor and says why no multiple of a can ever reach 1.
The inverse comes out of the extended Euclidean algorithm rather than a search, so a nine-digit modulus costs the same as a two-digit one, and every step is shown.
Results are checked against an exhaustive search over all pairs below sixty, refusals included, so the absence of an inverse is verified rather than assumed.
Add this calculator to your site
Responsive embed — and private: nothing your visitors type leaves their browser.