The modular inverse of a with respect to n is the number x satisfying a × x ≡ 1 mod n. It is the modular equivalent of a reciprocal, and it is what makes division possible in modular arithmetic, where dividing by a number is defined as multiplying by its inverse. This modular inverse calculator uses the extended Euclidean algorithm, prints every division step and the Bézout coefficients that come out of it, and states clearly when no inverse exists because the greatest common divisor is not one.
Arb Digital treated the non-existence case as the important one. Every pair of inputs produces a greatest common divisor, but only some produce an inverse, and a routine that returns a number regardless is producing something that will silently fail a verification step further down a pipeline. The tool reports the gcd first and the inverse second, in that order, because the first determines whether the second is even a meaningful question.
What This Modular Inverse Calculator Does
It runs the extended Euclidean algorithm on a and n. The plain Euclidean algorithm finds the greatest common divisor by repeated division with remainder; the extended version also tracks, at every step, how the current remainder can be written as a combination of the two original numbers. When the algorithm finishes, the greatest common divisor is expressed as ax + ny for integers x and y — the Bézout coefficients — and if that gcd is 1, then x reduced modulo n is the inverse.
Everything is computed in arbitrary-precision integers, so numbers of hundreds of digits are handled exactly. The results grid shows the gcd, both Bézout coefficients, and a verification: a multiplied by the returned inverse, reduced modulo n, which must come out as exactly 1 for a valid answer.
This is a different operation from those on the pages beside it. Our modulo calculator returns the remainder a mod n and nothing more. Our modular exponentiation calculator raises a to a power under a modulus. Finding an inverse is neither of those; it is solving an equation, and the algorithm that does it is unrelated to the one that does the other two.
How to Use It
- Enter a and the modulus. Both must be whole numbers, and the modulus has to be at least two for an inverse to be a meaningful question.
- Read the gcd before the inverse. If it is anything other than one, no inverse exists and the tool will say so instead of returning a value.
- Choose the answer range if it matters. The least non-negative form is standard in textbooks; the symmetric form is smaller in magnitude and appears in some implementations.
- Follow the division steps for coursework. The table lists each quotient and remainder, which is the working an examiner expects to see.
- Confirm with the verification figure. Multiplying a by the answer and reducing must give exactly one; anything else means the inputs were misread.
The Method and How It's Calculated
Take the default values: find the inverse of 17 modulo 3,120. The Euclidean algorithm divides repeatedly. 3,120 = 183 × 17 + 9. Then 17 = 1 × 9 + 8. Then 9 = 1 × 8 + 1. Then 8 = 8 × 1 + 0, so the last non-zero remainder is 1 and the greatest common divisor is 1. An inverse therefore exists.
Now work the remainders backwards. From the third line, 1 = 9 − 1 × 8. Substitute 8 = 17 − 1 × 9 from the second line: 1 = 9 − (17 − 9) = 2 × 9 − 17. Substitute 9 = 3,120 − 183 × 17 from the first: 1 = 2 × (3,120 − 183 × 17) − 17 = 2 × 3,120 − 367 × 17. So x = −367 and y = 2, and −367 modulo 3,120 is 2,753.
Check it: 17 × 2,753 = 46,801, and 46,801 − 15 × 3,120 = 46,801 − 46,800 = 1. The inverse is correct. Those particular numbers are the classic RSA textbook example, where 17 is the public exponent and 2,753 the private one derived from it. The extended algorithm and Bézout's identity are developed in the number theory unit of the MIT OpenCourseWare Mathematics for Computer Science course.
Why an Inverse Sometimes Does Not Exist
Suppose a and n share a common factor d greater than one. Then ax is a multiple of d for every integer x, and so is any multiple of n. If ax ≡ 1 mod n, then ax − 1 is a multiple of n, hence a multiple of d, and since ax is also a multiple of d, so is 1. Nothing greater than one divides 1, so d cannot exist. The assumption fails.
Concretely: 6 has no inverse modulo 9, because gcd(6, 9) = 3. Multiplying 6 by anything and reducing modulo 9 gives 0, 6 or 3 and never 1 — the multiples of 6 modulo 9 only ever land on multiples of 3. A calculator that returns something anyway is returning a number that fails its own verification, which is worse than returning nothing.
The practical rule follows immediately: every non-zero value has an inverse modulo n exactly when n is prime, because a prime shares no factor with anything below it. This is why prime moduli are used throughout cryptography, and why our prime number checker is a useful companion when you are choosing one. For composite moduli, the count of values that do have inverses is Euler's totient φ(n), and factoring n with our prime factorization calculator is how you compute it.
Bézout's Identity Is the Real Result
The extended Euclidean algorithm does not really compute an inverse. It computes integers x and y such that ax + ny = gcd(a, n), which is Bézout's identity, and the inverse is a corollary. Read that equation modulo n and the ny term vanishes, leaving ax ≡ gcd(a, n). When the gcd is 1, x is the inverse. When it is not, the equation still holds but tells you something different.
That broader result solves more than inverses. The linear congruence ax ≡ b mod n has a solution precisely when gcd(a, n) divides b, and when it does there are exactly gcd(a, n) distinct solutions modulo n. The inverse case is simply b = 1 with gcd = 1, which gives one solution. Knowing the general form saves you from concluding that an equation is unsolvable when it merely has multiple solutions.
The coefficients also give the smallest positive combination of the two numbers, which is the gcd itself — no smaller positive integer can be written as ax + ny. That is a genuinely useful fact in its own right, and it is why the algorithm turns up in problems about coin denominations, ruler-and-compass constructions and integer programming that have nothing obviously to do with modular arithmetic.
Where Modular Inverses Are Used
RSA key generation is the standard example. The private exponent d is defined as the modular inverse of the public exponent e with respect to φ(n), and the whole scheme rests on that single inverse computation. It is why the public exponent must be chosen coprime to φ(n) — otherwise no private key exists and the key pair cannot be formed at all.
The Chinese remainder theorem uses inverses to reassemble a value from its remainders modulo several coprime moduli, which is how RSA implementations speed up decryption by working modulo each prime factor separately. Elliptic curve cryptography needs a modular inverse for every point addition, which is why implementations go to considerable lengths to batch or avoid them.
Outside cryptography, modular inverses appear in hashing schemes, in reversible pseudorandom generators, in error-correcting codes over finite fields, and in the affine cipher, where decryption requires inverting the multiplier used to encrypt. Any scheme that multiplies by a constant and needs to undo it needs an inverse, and the coprimality requirement is what constrains which constants may be used. The role of these primitives in key establishment is set out in NIST SP 800-56A Rev. 3 on pair-wise key establishment.
Doing It the Slow Way, and When That Is Fine
For a small modulus you can simply try every value from 1 to n − 1 and stop when the product is congruent to 1. This is a search of n steps and is perfectly reasonable for a modulus in the hundreds. It also has a real advantage for learners: it makes visible that the inverse is defined by a property rather than produced by a formula.
The extended Euclidean algorithm needs about log n steps instead. For a 2,048-bit modulus that is a few thousand operations against a search that would never terminate. Fermat's little theorem offers a third route when the modulus is prime, since ap−2 ≡ a−1 mod p, and that can be evaluated by repeated squaring on our modular exponentiation calculator.
The exponentiation route is convenient but slower than the Euclidean one in most implementations, and it only applies to prime moduli. It has one compensating advantage in cryptographic code: it runs in a fixed number of steps regardless of the input, whereas the Euclidean algorithm branches on the data. That constant-time property matters when an attacker can measure how long the computation took.
Arb Digital builds and maintains web platforms with the edge cases handled rather than discovered later by a user.
See Our Web Work Talk To Our TeamCommon Mistakes to Avoid
- Assuming every number has an inverse — an inverse exists only when a and n are coprime, and a shared factor rules it out entirely.
- Reporting the raw Bézout coefficient — x often comes out negative, and it has to be reduced into the range 0 to n − 1 before it is the conventional answer.
- Confusing the inverse with the remainder — a mod n is what is left after division, while the inverse is what a must be multiplied by to leave one.
- Using floating-point arithmetic — the algorithm needs exact integer division and remainder, and doubles lose exactness past about sixteen digits.
- Forgetting the modulus in RSA is φ(n), not n — the private exponent inverts the public one modulo the totient, and using n instead produces a key that does not work.
Related Free Tools From Arb Digital
Take the plain remainder with the modulo calculator, raise to a power under a modulus with the modular exponentiation calculator, test a candidate modulus with the prime number checker, split a composite into its factors with the prime factorization calculator, or follow a division layout step by step on the long division calculator. The full free online tools hub lists every mathematics tool we publish.
Frequently Asked Questions
It is the number x for which a times x leaves a remainder of one when divided by the modulus. It plays the role of a reciprocal, which is what makes division possible in modular arithmetic.
Whenever a and the modulus share a common factor greater than one. Every multiple of a is then also a multiple of that factor, and no multiple of a factor above one can leave a remainder of one.
It runs the ordinary Euclidean algorithm while tracking how each remainder is built from the two original numbers. At the end the greatest common divisor is written as ax plus ny, and x is the inverse when that divisor is one.
The Bézout coefficient often comes out negative. Adding the modulus until it lands between zero and n minus one gives the conventional answer, and both values are congruent so either is technically correct.
Yes, every non-zero value does. A prime shares no factor with anything smaller than itself, so the coprimality condition is automatically satisfied, which is why prime moduli are used so widely.
Yes, when the modulus is prime. Raising a to the power p minus two gives the inverse, and it can be evaluated by repeated squaring, though this is usually slower than the Euclidean method.
The first is the remainder left when a is divided by n. The second is a different number entirely: the one that multiplies a to leave a remainder of exactly one.
This page explains a mathematical method for study and for checking your own working. It is not a substitute for showing your method, and it is not medical, legal, or financial advice.
