Modular Inverse Calculator

Results

17⁻¹ ≡ 2753 (mod 3120), because 17 × 2753 ≡ 1 (mod 3120).

Extended Euclidean algorithm

Start with the rows n and a. Each new row subtracts q times the row above from the row before it, in the r, s and t columns alike, until r reaches 0. Every row satisfies r = n·s + a·t.

The gcd is 1, so t is the inverse of a: −367 ≡ 2753 (mod 3120) once reduced into 0 … 3119.

Check: 17 × 2753 = 46801 = 15 × 3120 + 1.

How to Use the Modular Inverse Calculator

1. 1. Pick what to calculate. Modular inverse finds x with a·x ≡ 1 (mod n). Chinese remainder theorem solves several congruences at once.
2. 2. Enter the numbers. For an inverse, type a and the modulus n (at least 2). Negative a and a larger than n are fine — a is reduced first. For the Chinese remainder theorem, write one congruence per line, as 2 mod 3, x ≡ 2 (mod 3) or 2, 3.
3. 3. Read the answer. The inverse appears at the top, or No inverse with the gcd that blocks it. A system shows its smallest non-negative solution and how often the pattern repeats.
4. 4. Follow the working. The extended Euclidean table lists every quotient and remainder with the s and t coefficients; the congruence solver shows each merge, and the textbook M, Mᵢ, yᵢ table when the moduli are coprime.

What a Modular Inverse Is

The inverse of a modulo n is the number x, between 0 and n − 1, for which a × x leaves remainder 1 when divided by n. It plays the part that 1/a plays in ordinary arithmetic, so it is what lets you divide in modular arithmetic: a ÷ b mod n means a × b⁻¹ mod n. For example 3 × 4 = 12 ≡ 1 (mod 11), so 4 is the inverse of 3 modulo 11.

An inverse exists exactly when gcd(a, n) = 1. If a and n share a factor g > 1, every multiple of a shares it too, so a·x can never be 1 more than a multiple of n. When n is prime, every non-zero residue has an inverse. For 6 modulo 15 the gcd is 3, so the calculator reports that no inverse exists.

The Extended Euclidean Algorithm

Euclid's algorithm finds gcd(n, a) by repeated division. The extended version keeps two extra columns, s and t, that track how each remainder is built from the starting numbers: every row satisfies r = n·s + a·t. When the remainder reaches 0, the row before it holds the gcd, and its coefficients are Bézout's identity: n·s + a·t = gcd(n, a). If the gcd is 1, then a·t ≡ 1 (mod n), so t — reduced into the range 0 to n − 1 — is the inverse.

Worked Example: 17 Modulo 3120

This is the textbook RSA example: with the primes 61 and 53, n = 3233 and φ(n) = 60 × 52 = 3120, and the public exponent 17 needs the private exponent d = 17⁻¹ mod 3120.

i  q    r     s     t
0  —    3120  1     0
1  —    17    0     1
2  183  9     1     −183
3  1    8     −1    184
4  1    1     2     −367
5  8    0     −17   3120

The row before the zero gives 3120 × 2 + 17 × (−367) = 1, so gcd = 1 and t = −367. Adding 3120 puts it in range: 17⁻¹ ≡ 2753 (mod 3120). Check: 17 × 2753 = 46,801 = 15 × 3120 + 1.

The Chinese Remainder Theorem

If the moduli m₁, m₂, … are pairwise coprime, the system x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂), … always has exactly one solution modulo M = m₁ × m₂ × …. The classic puzzle from the Chinese text Sunzi Suanjing asks for a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5 and remainder 2 when divided by 7. Here M = 105, and the answer is x ≡ 23 (mod 105).

By the textbook formula, with Mᵢ = M ÷ mᵢ and yᵢ the inverse of Mᵢ modulo mᵢ: M₁ = 35 with y₁ = 2, M₂ = 21 with y₂ = 1, and M₃ = 15 with y₃ = 1. Then x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, and 233 mod 105 = 23.

When the moduli share factors the formula no longer works, but the system may still be solvable. The calculator merges the congruences two at a time: x ≡ 2 (mod 6) and x ≡ 8 (mod 10) agree, because gcd(6, 10) = 2 divides 8 − 2 = 6, and combine into x ≡ 8 (mod 30), repeating every lcm(6, 10) = 30. But x ≡ 1 (mod 6) with x ≡ 2 (mod 4) has no solution: gcd = 2 does not divide 1.

Frequently Asked Questions

When does a modular inverse exist?

Only when a and the modulus n are coprime, meaning gcd(a, n) = 1. Then the inverse is unique modulo n. If the gcd is larger than 1 — say 6 and 15, which share 3 — no whole number x makes 6x ≡ 1 (mod 15), and the calculator says so instead of guessing.

How do you find a modular inverse by hand?

Run the extended Euclidean algorithm on n and a, tracking the t column as in the table above. When the remainder hits 1, that row's t is the inverse (add n if it is negative). For small moduli you can also just try x = 1, 2, 3, … until a·x leaves remainder 1.

Is there another way to compute a modular inverse?

Yes, using Euler's theorem: a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1, so a⁻¹ ≡ a^{φ(n) − 1}. For a prime modulus p this is Fermat's little theorem: a⁻¹ ≡ a^{p − 2} (mod p). It needs φ(n), which requires factoring n, so the extended Euclidean algorithm is usually the better route.

Can a modular inverse be negative?

The extended Euclidean algorithm often produces a negative coefficient, like −367 for 17 modulo 3120. It is the same residue class as 2753, because they differ by 3120. By convention the inverse is reported in the range 0 to n − 1.

What do I do if the moduli in the Chinese remainder theorem are not coprime?

Check each pair for consistency: the congruences x ≡ a (mod m) and x ≡ b (mod k) agree exactly when gcd(m, k) divides b − a. If every pair agrees, a solution exists and is unique modulo the lcm of the moduli, not their product. The merging steps shown above do this for you.

How are modular inverses used in cryptography?

RSA's private exponent is the inverse of the public exponent modulo φ(n), as in the 17 modulo 3120 example. Modular inverses also appear in elliptic-curve arithmetic, in solving linear congruences, and in hashing schemes. Real RSA uses primes hundreds of digits long; this tool handles up to 60 digits.

How do I solve a linear congruence like 17x ≡ 5 (mod 3120)?

Multiply both sides by the inverse of 17: x ≡ 5 × 2753 = 13,765 ≡ 1285 (mod 3120). Find the inverse here first. If gcd(a, n) = g is larger than 1, a solution exists only when g divides the right-hand side, and then there are g solutions modulo n.