Inverso Modular

Modular inverse: definition and algorithm

Take an integer a and a modulus n. Its modular inverse is the integer a⁻¹ that makes a · a⁻¹ ≡ 1 (mod n) hold. Such a value turns up exactly when gcd(a, n) = 1, and the extended Euclidean algorithm finds it quickly.

Take 3⁻¹ mod 7 = 5. It checks out because 3 · 5 = 15 = 2 · 7 + 1. Euler's theorem gives another route, a⁻¹ ≡ a^(φ(n)−1) (mod n), and if n = p happens to be prime, Fermat's little theorem simplifies that to a⁻¹ ≡ a^(p−2) (mod p).

Applications

• RSA, where the private key d is just the inverse e⁻¹ mod φ(n).
• The Chinese Remainder Theorem (CRT), where combining residues leans on modular inverses.
• Cryptographic hashing and ECC arithmetic, both working over finite fields.
• Computer algebra, when you need to solve linear congruences like a x ≡ b (mod n).

FAQ

When does the inverse fail to exist? Whenever gcd(a, n) > 1. Take 6 modulo 9: there is no inverse, since gcd(6, 9) = 3.

Is the inverse unique? Modulo n, yes. Exactly one representative falls in the range [0, n − 1].

Euclidean or Fermat, which is faster? The extended Euclidean algorithm handles any modulus and runs in O(log n). Fermat's shortcut only works when n is prime and relies on modular exponentiation; it is also O(log n), but the constants are bigger.