A modular multiplicative inverse of an integer modulo an integer is an integer such that
Equivalently, divides . Such an inverse exists exactly when and are relatively prime, meaning that their greatest common divisor is 1. When it exists, the inverse is unique modulo and is commonly written . Modular inverses make division possible in modular arithmetic and are fundamental to computational number theory and cryptography.
Definition and examples
For example,
so 5 is an inverse of 3 modulo 7. Every integer congruent to 5 modulo 7, such as , 12, or 19, is also an inverse. Thus the inverse is unique as an equivalence class, not as an ordinary integer. A standard representative is chosen from .
By contrast, 2 has no inverse modulo 6. Every product is even, whereas every integer congruent to 1 modulo 6 is odd.
The notation in this setting does not generally denote the ordinary reciprocal in the rational numbers. It denotes an inverse with respect to multiplication modulo the specified modulus. The modulus is essential: the inverse of 3 modulo 7 is 5, while its inverse modulo 11 is 4.
Existence and uniqueness
The basic criterion is
If is an inverse, then , so there is an integer such that
Any common divisor of and must therefore divide 1, proving that their greatest common divisor is 1.
Conversely, Bézout’s identity states that if , there are integers and satisfying
Reducing this equation modulo gives , so is an inverse.
For uniqueness, suppose and . Multiplying the second congruence by and using gives .
These statements concern multiplicative inverses. Every residue has an additive inverse, namely , whether or not it has a multiplicative inverse.
Computing modular inverses
Extended Euclidean algorithm
The standard general-purpose method is the extended Euclidean algorithm. It augments the Euclidean algorithm by computing coefficients such that
If the greatest common divisor is 1, the coefficient , reduced modulo , is the required inverse. Otherwise, no inverse exists.
For example, to invert 17 modulo 43:
Back-substitution gives
Hence
After reducing modulo , the algorithm takes division steps. This is an arithmetic-operation count; its bit complexity also depends on the methods used for arithmetic on large integers.
Exponentiation
For a prime modulus , Fermat’s little theorem gives
whenever does not divide . Therefore,
For , the only nonzero residue is 1, which is its own inverse.
More generally, Euler’s theorem gives
when , where Euler’s totient function counts the invertible residue classes modulo . Consequently,
Repeated squaring computes these powers efficiently. For a general composite modulus, however, finding may require information not already available, such as a factorization of . The extended Euclidean algorithm requires no factorization.
Lifting an inverse to higher powers
An inverse modulo a prime power can be refined using a modular analogue of Newton’s method. If
define
Then
so
Each refinement doubles the exponent of the modulus to which the inverse is valid. This is useful for arithmetic modulo large prime powers, including powers of 2.
Modular division and linear congruences
If is invertible modulo , the congruence
has the unique solution
This is the modular counterpart of dividing both sides of an equation by .
Without an inverse, division cannot be performed in this way. Nevertheless, the congruence may still have solutions. Let . Then:
- If does not divide , there are no solutions.
- If divides , there are exactly distinct solutions modulo .
In the second case, dividing the integer coefficients and modulus by gives
whose coefficient is invertible modulo .
For example,
reduces to
Since , this gives , corresponding to the two solutions and .
This distinction also governs cancellation: cancelling a factor that is not invertible generally requires changing the modulus.
Algebraic interpretation
The residue classes modulo form the ring . Its invertible elements are called units. Under multiplication they form an abelian group, written
with elements.
If is prime, every nonzero residue is invertible, and is a finite field. If is composite, some nonzero residues are not invertible. Such residues are zero divisors: if and , then the nonzero residue satisfies
The Chinese remainder theorem gives a componentwise description. If with , then is invertible modulo exactly when it is invertible modulo both and . Its inverse modulo can be reconstructed from those two inverses.
Applications and implementation considerations
Modular inverses occur throughout exact computation:
- Cryptography: In RSA, the private exponent is chosen as an inverse of the public exponent modulo an appropriate exponent modulus.
- Reconstruction from residues: Constructive formulas for the Chinese remainder theorem use inverses to combine congruences.
- Linear algebra: A matrix over is invertible exactly when its determinant is a unit. For an integer matrix , this means .
- Polynomial computation: Division and interpolation over finite fields use multiplicative inverses of nonzero coefficients and evaluation-point differences.
- Batch inversion: A collection of invertible residues can be inverted using one inversion and a linear number of multiplications, by forming prefix products and then working backward.
Implementations must distinguish failure of invertibility from a valid result. Negative coefficients returned by the extended Euclidean algorithm are normally reduced to a standard nonnegative residue. Fixed-width arithmetic must also account for overflow in intermediate products.
In cryptographic computations involving secrets, the timing and memory-access patterns of an inversion algorithm can matter. Ordinary Euclidean implementations may follow data-dependent execution paths, so cryptographic implementations may instead use constant-time inversion methods.