Modular Inverse Calculator

Find a⁻¹ mod m when it exists.

FreeNo accountOn your device

Runs in your browser. How to verify

Loading tool…

About this tool

Enter a and a modulus m to find the number that multiplies with a to give 1 mod m. The inverse of 3 mod 11 is 4 because 3 × 4 = 12 = 1 + 11.

How to use

1
Step 1
Enter a.
2
Step 2
Enter the modulus m (greater than 1).
3
Step 3
Press Calculate.

How it works

An inverse exists only when a and m are coprime. The extended Euclidean algorithm finds it. In RSA, the private exponent is the inverse of the public exponent 17 modulo φ(n) = 3120, which is 2753.

a · a⁻¹ ≡ 1 (mod m)      exists  ⇔  GCD(a, m) = 1

Worked example

A textbook RSA pair

Input
a = 17, m = 3120
Output
2753
Walkthrough
17 × 2753 = 46,801, and 46,801 = 15 × 3120 + 1, so the remainder is 1.

Limitations

  • The modulus must be an integer greater than 1.
  • If GCD(a, m) is not 1, as with 6 mod 9, the tool reports that no inverse exists.
  • A negative a is reduced first: −3 mod 11 gives 7.

Questions

What is the inverse of 3 mod 11?
The inverse of 3 mod 11 is 4, because 3 × 4 = 12 ≡ 1 (mod 11).
What is the inverse of 17 mod 3120?
2753.
What is the inverse of -3 mod 11?
7, since −3 ≡ 8 and 8 × 7 = 56 = 5 × 11 + 1.
Why does 6 mod 9 have no inverse?
6 and 9 share the factor 3, so 6x can never be 1 mod 9.

Features

  • Extended Euclid
  • Coprime check
  • Runs in your browser

Related resources

Guides and videos from around the web—opens on YouTube or the publisher’s site.

  • Finding a percentage

    Khan Academy

    Percentage basics used across many calculator pages.

    Watch on YouTube
  • Derivative as a concept

    Khan Academy

    When general calculators hand off to calculus tools.

    Watch on YouTube
  • OpenStax Math

    OpenStax

    Free textbooks for algebra through calculus.

  • Data Index

    Math is Fun

    Stats and probability explainers for data tools.