Key takeaways
- The inverse of a modulo n is a number x with ax ≡ 1 (mod n); it exists exactly when gcd(a, n) = 1.
- The extended Euclidean algorithm writes 1 = ax + ny, and then x, reduced mod n, is the inverse.
- Example: 17 × 38 = 646 = 15 × 43 + 1, so the inverse of 17 modulo 43 is 38.
- For a prime modulus p, Fermat's little theorem gives the inverse directly as aᵖ⁻² mod p.
- Once you have the inverse, ax ≡ b (mod n) is solved by multiplying both sides by it.
In ordinary arithmetic, dividing by 3 means multiplying by 1/3. Modular arithmetic has no fractions, but it has something that does the same job: a number that multiplies with 3 to give 1. Modulo 7 that number is 5, since 3 × 5 = 15 ≡ 1. It is called the modular inverse of 3, and finding inverses is how you "divide" when working mod n, which is why they matter in everything from solving congruences to RSA encryption.
The definition and when it exists
The inverse of a modulo n is an integer x with
ax ≡ 1 (mod n).
It exists if and only if gcd(a, n) = 1. MathWorld states it this way: a nonzero integer has an inverse modulo n if and only if the two are relatively prime. Modulo 4, for example, 2 has no inverse, since 2x is always even and so never leaves remainder 1. The reason is short. If d = gcd(a, n) > 1, then d divides both a and n, so d divides ax − kn for any integers x and k. That expression can never equal 1, so ax ≡ 1 (mod n) has no solution.
So modulo a prime p, every number from 1 to p − 1 has an inverse; modulo 5, MathWorld lists the inverses of 1, 2, 3 and 4 as 1, 3, 2 and 4. Modulo a composite number, only the numbers coprime to it do. Modulo 15, for example, 6 has no inverse because gcd(6, 15) = 3.
Method: the extended Euclidean algorithm
The Euclidean algorithm finds gcd(a, n). Running its steps backwards writes the gcd as a combination ax + ny, the result Applied Discrete Structures states as Bézout's lemma. When the gcd is 1,
ax + ny = 1, so ax ≡ 1 (mod n),
and x is the inverse.
Worked example: the inverse of 17 modulo 43.
Forward, the Euclidean algorithm:
| Division | Remainder |
|---|---|
| 43 = 2 × 17 + 9 | 9 |
| 17 = 1 × 9 + 8 | 8 |
| 9 = 1 × 8 + 1 | 1 |
The gcd is 1, so an inverse exists. Now work backwards, writing each remainder in terms of the earlier numbers:
- 1 = 9 − 8
- 8 = 17 − 9, so 1 = 9 − (17 − 9) = 2 × 9 − 17
- 9 = 43 − 2 × 17, so 1 = 2 × (43 − 2 × 17) − 17 = 2 × 43 − 5 × 17
So −5 × 17 ≡ 1 (mod 43). The inverse is −5, or 38 after adding 43. Check: 17 × 38 = 646 = 15 × 43 + 1.
Always do the check. Sign errors in the back-substitution are the usual mistake, and a single multiplication catches them.
A second example: the inverse of 7 modulo 26
A modulus of 26, one remainder for each letter of the alphabet, is a natural choice for letter-shuffling puzzles, and the back-substitution takes one more step than before.
- 26 = 3 × 7 + 5
- 7 = 1 × 5 + 2
- 5 = 2 × 2 + 1
Back-substitute: 1 = 5 − 2 × 2 = 5 − 2 × (7 − 5) = 3 × 5 − 2 × 7 = 3 × (26 − 3 × 7) − 2 × 7 = 3 × 26 − 11 × 7.
So the inverse of 7 is −11 ≡ 15 (mod 26). Check: 7 × 15 = 105 = 4 × 26 + 1.
Shortcut for a prime modulus
If p is prime and a is not a multiple of p, Fermat's little theorem says aᵖ⁻¹ ≡ 1 (mod p). Then a × aᵖ⁻² ≡ 1, so
a⁻¹ ≡ aᵖ⁻² (mod p).
Modulo 7, the inverse of 3 is 3⁵ = 243 ≡ 5, as found at the start. For large primes, compute the power by repeated squaring, covered in modular arithmetic. The extended Euclidean algorithm also works for composite moduli, so it is the general-purpose method.
Solving a linear congruence
To solve ax ≡ b (mod n) when gcd(a, n) = 1, multiply both sides by the inverse of a:
x ≡ a⁻¹ · b (mod n).
Example. Solve 17x ≡ 5 (mod 43). The inverse of 17 is 38, so x ≡ 5 × 38 = 190 ≡ 190 − 172 = 18 (mod 43). Check: 17 × 18 = 306 = 7 × 43 + 5.
Levin's Discrete Mathematics: An Open Introduction solves small congruences such as 3x + 2 ≡ 4 (mod 5) both by trying every remainder and by algebra with congruences. Trying every remainder is fine for a modulus of 5; for a modulus of 43 it means up to 43 trials, and the inverse is quicker.
When gcd(a, n) = d > 1. Then ax ≡ b (mod n) has a solution only if d divides b. For 6x ≡ 9 (mod 15), d = 3 divides 9, so divide everything by 3 to get 2x ≡ 3 (mod 5), whose solution is x ≡ 4 (mod 5), giving three solutions mod 15: 4, 9 and 14. For 6x ≡ 5 (mod 15), 3 does not divide 5, so there is no solution.
Where modular inverses are used
- Solving systems of congruences, in the construction behind the Chinese remainder theorem.
- RSA, where, in MathWorld's description, the private and public keys are chosen so that their product is congruent to 1 modulo the totient of the product of the two primes.
- Undoing a function. Multiplying by an inverse undoes multiplication, exactly as in composition and inverse functions: the map x ↦ ax is a bijection on the remainders mod n precisely when a is invertible.
Inverses to find
- Find the inverse of 5 modulo 12. (5 × 5 = 25 ≡ 1, so 5 is its own inverse.)
- Find the inverse of 11 modulo 26. (19, since 11 × 19 = 209 = 8 × 26 + 1.)
- Does 9 have an inverse modulo 12? Explain.
- Solve 8x ≡ 3 (mod 13).
Discrete Math: Study & Quiz has a unit on number theory and modular arithmetic, with lessons, knowledge checks and topic quizzes. Find it with our education apps, and the full number theory sequence in the discrete math hub.
Good to know
Frequently asked questions
What is a modular inverse?
When does a modular inverse exist?
How do you find a modular inverse quickly?
How do I solve 17x ≡ 5 (mod 43)?
Sources
- Modular Inverse (opens in a new tab)Wolfram MathWorld — accessed
- Greatest Common Divisors and the Integers Modulo n: Bézout's Lemma (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
- Introduction to Number Theory: Solving Congruences (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
- RSA Encryption (opens in a new tab)Wolfram MathWorld — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.