Introduction

A modular multiplicative inverse of a modulo m is a number x such that a * x mod m = 1. It exists only when a and m are coprime. In Python, you can compute it with the extended Euclidean algorithm, and in modern Python you can also use the built-in pow function directly.

The Mathematical Condition

The inverse exists if and only if gcd(a, m) = 1.

Example:

• inverse of 3 mod 11 exists because gcd(3, 11) = 1
• inverse of 6 mod 15 does not exist because gcd(6, 15) = 3

That condition matters because modular inverse is not defined for every pair of integers.

Extended Euclidean Algorithm

The most general algorithm is the extended Euclidean algorithm. It finds integers x and y such that:

• 'a * x + m * y = gcd(a, m)'

If the gcd is 1, then x is the modular inverse of a modulo m.

1def extended_gcd(a, b):
2    if a == 0:
3        return b, 0, 1
4    gcd, x1, y1 = extended_gcd(b % a, a)
5    x = y1 - (b // a) * x1
6    y = x1
7    return gcd, x, y
8
9
10def mod_inverse(a, m):
11    gcd, x, _ = extended_gcd(a, m)
12    if gcd != 1:
13        raise ValueError("inverse does not exist")
14    return x % m
15
16
17print(mod_inverse(3, 11))

This prints 4, because 3 * 4 = 12 and 12 mod 11 = 1.

Built-In Python Shortcut

Modern Python has a very convenient option:

print(pow(3, -1, 11))

This also prints 4.

It is concise and usually the best choice when you simply need the inverse. If the inverse does not exist, Python raises an error rather than returning a meaningless value.

Fermat's Little Theorem

If the modulus is prime and a is not divisible by that prime, Fermat's little theorem gives another approach:

• 'a^(m-2) mod m'

print(pow(3, 11 - 2, 11))

This works for m = 11 because 11 is prime.

It is a useful technique in competitive programming and number theory code, but the extended Euclidean algorithm or pow(a, -1, m) is usually more general and easier to explain.

Practical Uses

Modular inverses appear in:

• RSA and other cryptographic algorithms
• modular division in number theory
• combinatorics under a prime modulus
• solving linear congruences

For example, if you need to compute a / b mod m, you often rewrite it as a * inverse(b) mod m, assuming the inverse exists.

b_inv = pow(7, -1, 13)
result = (5 * b_inv) % 13
print(result)

This computes the modular version of dividing 5 by 7 modulo 13.

Negative Values and Normalization

The inverse returned by the extended Euclidean algorithm may be negative before normalization. That is normal.

For instance, if x = -7 is a valid algebraic solution, x % m converts it into the standard nonnegative representative in the range 0 through m - 1.

That is why return x % m appears in most implementations.

Common Pitfalls

The biggest mistake is trying to compute a modular inverse when a and m are not coprime.

Another mistake is using the Fermat shortcut with a modulus that is not prime.

A third issue is forgetting to normalize a negative inverse into the usual modular range.

Summary

• A modular inverse exists only when gcd(a, m) = 1
• The extended Euclidean algorithm is the general-purpose way to compute it
• In modern Python, pow(a, -1, m) is the simplest built-in option
• Fermat's little theorem works when the modulus is prime
• Normalize the result with % m so the inverse is returned in the expected range