Nirmion
ヘルプ ツールを探す

NUMBER THEORY / EXTENDED EUCLIDEAN ALGORITHM

Modular Multiplicative Inverse Calculator

Find the least nonnegative x satisfying a times x congruent to one modulo m.

  • 01 Calculated in this tab
  • 02 Values stay in this browser tab
  • 03 Use boundary

Conversion input

Known value

Filter by unit name, symbol, or code. Your current selections remain available.

Integer inputs

Preparing the calculator...

METHOD / WORKED EXAMPLE

Prove the inverse with its product residue

A modular inverse is not ordinary reciprocal division. It is an integer residue that multiplies by a to leave remainder one under the selected modulus, and it exists only for coprime inputs.

WORKED DEFAULT

Check the calculation with the default inputs

For a = 3 and modulus 11, the least nonnegative inverse is 4 because 3 x 4 = 12 and 12 modulo 11 leaves the verification residue 1.

  1. Normalize the input3 modulo 11 = 3
  2. Solve the Bezout relation4 is the inverse candidate
  3. Verify the residue3 x 4 modulo 11 = 1

READ THE RESULT

Interpret the output in context

The inverse represents a residue class: adding any multiple of the modulus gives an equivalent solution. This page reports the unique representative from zero through m minus one.

ASSUMPTIONS AND LIMITS

Know where the model stops

  • a and m are safe integers.
  • The modulus is greater than one.
  • gcd(a,m) equals one for a solution to exist.

An inverse exists only when gcd(a,m) = 1. This bounded educational implementation is not a cryptographic primitive.

NIST DLMF: Multiplicative number theory

COMMON QUESTIONS

Modular Multiplicative Inverse Calculator FAQs

Why does an inverse require gcd(a,m) = 1?

The equation a x + m y = 1 has integer solutions exactly when the greatest common divisor of a and m divides one, which means that gcd must be one. If they share a larger factor, every integer combination remains divisible by that factor and cannot equal one, so no product residue of one exists.

Why is the reported inverse always nonnegative?

All integers differing by a multiple of m represent the same residue class. The extended Euclidean algorithm may first produce a negative coefficient, so the calculator normalizes it into the standard range from zero through m minus one. That choice makes comparisons predictable without changing the underlying congruence or verification product.

Is modular inverse the same as dividing modulo m?

Multiplying by an inverse is how modular division can be defined when the divisor is coprime to the modulus. It is not ordinary fractional division, and division is not valid when no inverse exists. Normalize each operand, confirm coprimality, and verify the final congruence instead of applying real-number reciprocal rules to residues.

Use boundary

Calculation path

Normalize a into the least nonnegative residue class, use the extended Euclidean algorithm, reject gcd(a,m) other than one, and verify the product residue.

Calculation path

Find x such that a x x is congruent to 1 modulo m using the extended Euclidean algorithm.