Multiplicative inverse modulo n

The multiplicative inverse of an integer modulo n is the residue inverse that satisfies integer times inverse congruent to one modulo n. That inverse exists if and only if the integer and the modulus are coprime—their greatest common divisor is one. Cryptography tutorials, RSA private-key steps, modular division in contest programming, and cyclic-group calculations all need this operation, yet many languages only expose a binary GCD and leave the Bézout coefficients to you. This calculator takes the integer and the modulus, runs the extended Euclidean algorithm deterministically, and returns the unique non-negative inverse in the range zero through n minus one, together with the reduced residue, the gcd, and a check product so you can verify the result without re-deriving the steps.

What a multiplicative inverse modulo n is and when it exists

In ordinary arithmetic every non-zero number has a multiplicative inverse: divide by it and you get one. In modular arithmetic the same idea becomes a congruence. We say inverse is a multiplicative inverse of an integer modulo n when integer times inverse leaves remainder one when divided by the modulus.

Because residues wrap around every n steps, not every integer has such an inverse. The obstruction is number-theoretic rather than floating-point: if d equals the gcd of the integer and the modulus and d is greater than one, then the integer times any candidate is a multiple of d, so the product can never be congruent to one, which is not a multiple of d.

Conversely, Bézout’s identity guarantees integers x and y with integer times x plus modulus times y equal to one exactly when that gcd is one, and reducing x modulo n yields the inverse. Engineers meet this condition when they divide in a finite ring, when they choose RSA decryption exponents that invert the public exponent modulo phi of N, when they undo modular multiplications in hash pipelines, or when they solve linear congruences in competitive programming.

Returning an explicit error when the pair is not coprime is more useful than a silent failure: the client learns that no inverse exists and can branch on the gcd instead of guessing which of several libraries returned a wrong residue. The calculator therefore treats a non-coprime pair as invalid input rather than inventing a placeholder inverse that would break any later check of the defining congruence.

How this calculator runs the extended Euclidean algorithm

Call the capability with integer fields integer and modulus, where the modulus is at least two. The implementation first reduces the integer into the non-negative residue class residue in zero through n minus one, then applies the extended Euclidean algorithm to the pair residue and modulus. Each step records the integer quotient and updates the Bézout coefficients so that at termination the coefficient of residue multiplies residue plus a coefficient of the modulus equals the gcd.

If the gcd is one, the coefficient of residue is reduced into the range zero through n minus one and returned as inverse. Absolute values are bounded by one trillion so every intermediate doubling in the modular product stays inside JavaScript safe-integer range. Negative integers are accepted and reduced before the Euclidean loop, so an input of negative three modulo eleven is treated as residue eight and inverted in that class.

Practical use, limits, pricing, and delivery

Use the browser tool when you want a quick inverse while reading a crypto note, checking a homework congruence, or debugging a modular multiplication step. Accepted inputs are integers whose absolute value is at most one trillion and moduli from two through one trillion. Results are deterministic: the same pair always yields the same inverse and the same check field.

Keep the pair inside the published bounds, treat a not-coprime error as a first-class outcome in your tests, and you get a reproducible inverse for homework, LMS plugins, and edge workers without standing up a computer-algebra system of your own.