Multiplicative inverse in modular arithmetic calculator

a (integer)

m (modulus, integer ≠ 0)

Method Extended Euclidean Binary Extended Euclidean Fermat (prime modulus only)

Show factor insights

Batch input (optional): one pair per line as "a, m"

Separators accepted: comma, semicolon, or space.

Or upload CSV (columns: a,m)

Compute inverse Download CSV Download PDF Random demo

Enter values and press Compute inverse to see results here.

1. Find inverse: For a=17, m=43, the calculator returns 38. Verification: 17 × 38 ≡ 1 (mod 43).
2. Modular division: Compute 23 ÷ 17 (mod 43) as 23 × inv(17) (mod 43) = 14.
3. Large composite modulus: Invert 17 modulo 3120. Result: 2753. Check: 17 × 2753 ≡ 1 (mod 3120).

You can reproduce each step: enter the values above, select a method, and compare the verification column with these results.

The inverse of a modulo m is a number x satisfying a·x ≡ 1 (mod m). It exists iff gcd(a,m)=1.

• Extended Euclidean: Solve x·a + y·m = gcd(a,m). If gcd=1, inverse is x mod m.
• Binary EEA: Uses subtraction and halving for efficient coefficient updates.
• Fermat (prime m): If m is prime and a not divisible by m, then a^(m-2) mod m equals the inverse.

1. Enter integers for a and m. Modulus must be nonzero.
2. Choose a method: prefer Extended Euclidean; Binary is also robust.
3. Check “factor insights” to see prime-power analysis and partial inverses.
4. Use batch area or upload CSV for many pairs.
5. Export your results as CSV or PDF for sharing.

• If gcd(a, m) ≠ 1, inverse does not exist; show gcd and Bézout.
• Negative a are normalized: result in [0, m−1] for clarity.
• Fermat method auto-checks primality to prevent misuse.

1) When does a modular inverse exist?

For a modulo m, an inverse exists only when gcd(a, m) = 1. If the gcd is not one, the equation a·x ≡ 1 (mod m) has no solution, and modular division by a is undefined.

2) Which method should I choose?

Extended Euclidean is the default, fast, and deterministic for any modulus. Binary EEA avoids divisions using shifts. Fermat’s method works only for prime moduli and uses fast exponentiation a^(p−2) mod p.

3) Can I use negative a values?

Yes. The calculator normalizes inputs and outputs into the standard residue class. The reported inverse is always shown within the range [0, m−1] to simplify verification and downstream computations.

4) Why does Fermat fail sometimes?

Fermat’s method requires a prime modulus p and a not divisible by p. If the modulus is composite, a^(p−2) mod p is invalid. The tool auto-checks primality and warns to prevent misuse.

5) How do I solve a·x ≡ b (mod m)?

First compute a’s inverse modulo m, provided gcd(a, m) = 1. Then x ≡ b·a^(−1) (mod m). Enter a and m, get the inverse, and multiply by b modulo m to obtain the solution.

6) What if gcd(a, m) ≠ 1 but I still need a solution?

There is no inverse, but a·x ≡ b (mod m) may have solutions if gcd(a, m) divides b. Reduce by the gcd and solve in the smaller modulus, or factor m and use the Chinese Remainder Theorem.

7) How large can inputs be?

This tool handles typical 64‑bit sized moduli comfortably. Extended Euclid and Binary EEA scale logarithmically. For extremely large cryptographic sizes, specialized big‑integer libraries and optimized number‑theoretic implementations are recommended.