Modular Inverse Explained: How to Find an Inverse Modulo n

The modular inverse of a modulo n is the number x that satisfies a · x ≡ 1 (mod n). It exists if and only if gcd(a, n) = 1, and it plays the role that division plays in ordinary arithmetic. The inverse of 3 modulo 20 is 7, because 3 × 7 = 21 and 21 leaves a remainder of 1 on division by 20.

Modular arithmetic has no division. What it has instead is this: a number that undoes a multiplication. Once you have it, “dividing by 3” becomes “multiplying by 7”, and congruences can be solved the same way ordinary equations are.

This guide gives the existence test, then four ways to find an inverse, from inspection through to the general algorithm, each with worked examples and a verification step.

What a Modular Inverse Is

In ordinary arithmetic, the inverse of 4 is 1/4, because 4 × 1/4 = 1. Modular arithmetic has no fractions, so the definition is rewritten using congruence:

x is the modular inverse of a modulo n when a · x ≡ 1 (mod n).

The inverse is usually written a⁻¹ (mod n), and it is a whole number between 0 and n − 1, not a fraction.

Example. Modulo 20:

3 × 7 = 21 = 20 × 1 + 1        so 3 × 7 ≡ 1 (mod 20)

So 7 is the inverse of 3 modulo 20, and 3 is the inverse of 7 modulo 20. Inverses always come in pairs.

The idea behind modular arithmetic is that numbers wrap around at n. The inverse is the value that brings a product all the way back to 1.

When Does an Inverse Exist?

Not every number has one, and the test is simple.

a has an inverse modulo n if and only if gcd(a, n) = 1, that is, if a and n are coprime.

Why. If a and n share a factor d greater than 1, then every multiple of a is also a multiple of d once reduced modulo n. Since 1 is not a multiple of d, no multiple of a can ever be congruent to 1.

Example of failure. Does 6 have an inverse modulo 15?

gcd(6, 15) = 3

Not 1, so no inverse exists. Checking by hand confirms it: the multiples of 6 modulo 15 run 6, 12, 3, 9, 0 and then repeat, never reaching 1.

Two consequences follow immediately:

• If n is prime, every number from 1 to n − 1 has an inverse, since a prime shares no factor with anything below it.
• If n is composite, only the numbers coprime to n have one. Modulo 15, that excludes 3, 5, 6, 9, 10 and 12.

Method 1: Inspection

For a small modulus, multiply a by 1, 2, 3 and so on until the product leaves a remainder of 1. It takes at most n − 1 tries.

Problem. Find the inverse of 5 modulo 12.

5 × 1 = 5   ≡ 5   (mod 12)
5 × 2 = 10  ≡ 10  (mod 12)
5 × 3 = 15  ≡ 3   (mod 12)
5 × 4 = 20  ≡ 8   (mod 12)
5 × 5 = 25  ≡ 1   (mod 12)     found

Answer. 5⁻¹ ≡ 5 (mod 12). A number can be its own inverse, and this is one of those cases.

A shortcut for this method: instead of multiplying up, look for a multiple of n that is one more than a multiple of a. For 5 modulo 12, the multiples of 12 plus 1 are 13, 25, 37, 49; the first one divisible by 5 is 25, and 25 ÷ 5 = 5.

Inspection is fine up to a modulus of about 30. Beyond that it becomes tedious and you want Method 3.

Method 2: An Inverse Table

When the same modulus comes up repeatedly, build the table once.

Inverses modulo 11. Since 11 is prime, every value from 1 to 10 has one.

Read it in either direction: the inverse of 3 is 4, and the inverse of 4 is 3.

Two entries always look like this. 1 is always its own inverse, since 1 × 1 = 1. And n − 1 is always its own inverse, because n − 1 ≡ −1, and (−1) × (−1) = 1. That accounts for the first and last columns of any such table.

Spot-check one entry: 5 × 9 = 45 = 11 × 4 + 1. ✓

Method 3: The Extended Euclidean Algorithm

This is the method that works for any size of modulus and is what software uses. It runs the ordinary Euclidean algorithm to confirm gcd(a, n) = 1, then works backwards to express that 1 in terms of a and n.

Problem. Find the inverse of 17 modulo 43.

Step 1: Run the Euclidean algorithm on 43 and 17, recording each division.

43 = 2 × 17 + 9
17 = 1 ×  9 + 8
 9 = 1 ×  8 + 1
 8 = 8 ×  1 + 0     ← stop

The last non-zero remainder is 1, so gcd(43, 17) = 1 and an inverse exists.

Step 2: Back-substitute. Start from the equation whose remainder is 1 and work upward, replacing each remainder with what produced it.

1 = 9 − 1 × 8

8 = 17 − 1 × 9, so substitute:
1 = 9 − (17 − 9) = 2 × 9 − 17

9 = 43 − 2 × 17, so substitute:
1 = 2 × (43 − 2 × 17) − 17
  = 2 × 43 − 5 × 17

Step 3: Read off the inverse. The identity is

2 × 43 − 5 × 17 = 1

Reduce modulo 43. The term 2 × 43 vanishes, leaving −5 × 17 ≡ 1 (mod 43), so the inverse is −5. Convert to the standard range by adding 43:

-5 + 43 = 38

Answer. 17⁻¹ ≡ 38 (mod 43).

Verification. 17 × 38 = 646, and 646 = 43 × 15 + 1. ✓

The algorithm itself, including the tabular version that avoids back-substitution entirely, is covered in full in the extended Euclidean algorithm guide. The Euclidean Algorithm Calculator runs both directions on any pair of numbers.

Method 4: Fermat’s Little Theorem (Prime Modulus Only)

When the modulus is prime, a power calculation gives the inverse directly.

Fermat’s little theorem. If p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p).

Dividing both sides by a gives the inverse:

a⁻¹ ≡ a^(p−2)  (mod p)

Problem. Find the inverse of 5 modulo 13.

Here p = 13, so the inverse is 5¹¹ mod 13. Computing that directly would be painful, so reduce along the way:

5²  = 25 ≡ 12 ≡ −1   (mod 13)
5⁴  = (5²)² ≡ (−1)² = 1   (mod 13)
5⁸  = (5⁴)² ≡ 1      (mod 13)

5¹¹ = 5⁸ × 5² × 5¹ ≡ 1 × (−1) × 5 = −5 ≡ 8   (mod 13)

Answer. 5⁻¹ ≡ 8 (mod 13).

Verification. 5 × 8 = 40 = 13 × 3 + 1. ✓

The condition matters. This method is only valid when the modulus is prime. Applying it to a composite modulus gives a wrong answer with no warning. The systematic way to compute a^(p−2) for a large prime is repeated squaring, covered in modular exponentiation.

The Euler version for composite moduli

Euler’s theorem generalises Fermat’s: if gcd(a, n) = 1 then a^φ(n) ≡ 1 (mod n), where φ(n) counts the integers from 1 to n that are coprime to n. So

a⁻¹ ≡ a^(φ(n) − 1)  (mod n)

Problem. Find the inverse of 7 modulo 20.

The numbers coprime to 20 are 1, 3, 7, 9, 11, 13, 17 and 19, so φ(20) = 8, and the inverse is 7⁷ mod 20:

7²  = 49 ≡ 9    (mod 20)
7⁴  = 9² = 81 ≡ 1   (mod 20)
7⁷  = 7⁴ × 7² × 7 ≡ 1 × 9 × 7 = 63 ≡ 3   (mod 20)

Answer. 7⁻¹ ≡ 3 (mod 20). Check: 7 × 3 = 21 ≡ 1. ✓

This works, but it needs φ(n), which needs the factorisation of n. For large n that is harder than just running the extended Euclidean algorithm, so Method 3 remains the practical default.

Choosing a Method

The extended Euclidean algorithm is the only one with no conditions attached, which is why it is the standard answer.

Using an Inverse to Solve a Congruence

This is what inverses are for. A linear congruence is solved by multiplying both sides by the inverse of the coefficient.

Problem. Solve 5x ≡ 3 (mod 12).

The inverse of 5 modulo 12 is 5, found above. Multiply both sides by it:

5 × 5x ≡ 5 × 3   (mod 12)
   25x ≡ 15      (mod 12)
     x ≡ 3       (mod 12)

Answer. x ≡ 3 (mod 12).

Verification. 5 × 3 = 15 = 12 + 3, so 15 ≡ 3 (mod 12). ✓

The step 25x ≡ x works because 25 ≡ 1 (mod 12), which is exactly the property that makes 5 an inverse.

A congruence with no solution. Try 6x ≡ 4 (mod 15). Since gcd(6, 15) = 3, there is no inverse of 6, so this method does not apply. In fact the congruence has no solution at all. Running x through 0, 1, 2, 3, 4 gives 6x ≡ 0, 6, 12, 3, 9 and the pattern then repeats, so every possible value is a multiple of 3. The target 4 is not a multiple of 3, so it never appears.

Where Inverses Show Up

• The Chinese Remainder Theorem. The construction formula needs one inverse per congruence, and the substitution method needs one per merge. See Chinese Remainder Theorem.
• RSA cryptography. The private key is the inverse of the public exponent modulo φ(n). Encryption and decryption undo each other for exactly this reason.
• Solving linear congruences, as above, which is the modular version of solving ax = b.
• Affine ciphers. Decrypting a substitution of the form y = ax + b requires the inverse of a modulo the alphabet size.
• Hash and checksum design, where reversible mixing steps rely on multipliers that are coprime to the word size.

Common Modular Inverse Mistakes

• Assuming an inverse always exists. Check gcd(a, n) = 1 first. Modulo 12, the numbers 2, 3, 4, 6, 8, 9 and 10 have none.
• Reporting a negative value. The back-substitution often produces something like −5. Add the modulus to bring it into the range 0 to n − 1.
• Applying Fermat’s little theorem to a composite modulus. It is only valid for prime p, and it fails silently otherwise.
• Inverting the modulus instead of the number. You want a⁻¹ mod n, not n⁻¹ mod a.
• Confusing the inverse with the negative. The inverse of 3 modulo 20 is 7, not −3 or 17.
• Cancelling without an inverse. From 4x ≡ 4y (mod 12) you cannot conclude x ≡ y, because 4 has no inverse modulo 12.
• Skipping the check. Multiplying a by your answer and reducing takes five seconds and catches every arithmetic slip.

Modular Inverse Practice Problems

For each, decide whether an inverse exists and find it if it does.

1. 7 modulo 26
2. 9 modulo 31
3. 4 modulo 15
4. 13 modulo 40
5. 8 modulo 12
6. 23 modulo 100
7. 6 modulo 35
8. Solve 11x ≡ 5 (mod 26).

Answers

1. gcd(7, 26) = 1. Testing multiples: 7 × 15 = 105 = 26 × 4 + 1, so 7⁻¹ ≡ 15 (mod 26).
2. gcd(9, 31) = 1. 9 × 7 = 63 = 31 × 2 + 1, so 9⁻¹ ≡ 7 (mod 31).
3. gcd(4, 15) = 1. 4 × 4 = 16 ≡ 1, so 4⁻¹ ≡ 4 (mod 15). Another self-inverse.
4. gcd(13, 40) = 1. 13 × 37 = 481 = 40 × 12 + 1, so 13⁻¹ ≡ 37 (mod 40).
5. gcd(8, 12) = 4, which is not 1, so no inverse exists.
6. gcd(23, 100) = 1. Running the Euclidean algorithm: 100 = 4 × 23 + 8, then 23 = 2 × 8 + 7, then 8 = 1 × 7 + 1. Back-substituting gives 1 = 8 − 7 = 8 − (23 − 2 × 8) = 3 × 8 − 23 = 3(100 − 4 × 23) − 23 = 3 × 100 − 13 × 23. So 23⁻¹ ≡ −13 ≡ 87 (mod 100). Check: 23 × 87 = 2001 = 100 × 20 + 1. ✓
7. gcd(6, 35) = 1. 6 × 6 = 36 ≡ 1, so 6⁻¹ ≡ 6 (mod 35).
8. The inverse of 11 modulo 26 is 19, since 11 × 19 = 209 = 26 × 8 + 1. Multiplying both sides by 19 gives x ≡ 95 (mod 26), and 95 = 26 × 3 + 17, so x ≡ 17 (mod 26). Check: 11 × 17 = 187 = 26 × 7 + 5. ✓

Modular Inverse FAQ

What is a modular inverse in simple terms?

It is the number that multiplies a back to 1 within a fixed wrap-around range. Modulo 20, the inverse of 3 is 7 because 3 × 7 = 21, which wraps around to 1. It is the closest thing modular arithmetic has to a reciprocal.

How do you know if a modular inverse exists?

Compute gcd(a, n). If it equals 1, an inverse exists and is unique in the range 0 to n − 1. If it is anything greater than 1, no inverse exists. That single test settles the question before any work begins.

What is the fastest way to find a modular inverse?

For a small modulus, testing multiples is fastest in practice. For anything large, the extended Euclidean algorithm is the standard method, because it runs in roughly the number of digits rather than the size of the modulus.

Can a number be its own modular inverse?

Yes. 5 is its own inverse modulo 12, since 25 ≡ 1. So is 1 modulo any n, and so is n − 1, because n − 1 ≡ −1 and squaring −1 gives 1.

Is the modular inverse the same as a negative number?

No. The inverse of a is the number x with a·x ≡ 1, while the negative of a is the number with a + (−a) ≡ 0. Modulo 20, the inverse of 3 is 7 and the negative of 3 is 17. Different operations, different answers.

Why doesn’t every number have an inverse modulo n?

Because a number sharing a factor with n can never reach 1 by multiplication. Modulo 15, every multiple of 6 is a multiple of 3 once reduced, and 1 is not a multiple of 3. Only numbers coprime to n avoid this trap.

How many numbers have an inverse modulo n?

Exactly φ(n) of them, where φ is Euler’s totient function. Modulo 12 there are 4: the values 1, 5, 7 and 11. Modulo a prime p there are p − 1, meaning every non-zero value.

How is this related to dividing with a remainder?

Both start from the same division identity, but they ask opposite questions. Ordinary division asks what is left over, as in how to find the remainder. A modular inverse asks which multiplier leaves exactly 1, which is what makes it usable as a substitute for division.