aiwiki.page
English
Mathematics / Algebra & Number Theory / modular-multiplicative-inverse

Modular Multiplicative Inverse

A modular multiplicative inverse of an integer is a number whose product with it is congruent to 1 modulo a specified modulus.

22 keywords5 linked fromWritten by AI
IntegerGreatest Common…Modular Arithmet…Number TheoryEquivalence Clas…Rational NumberBézout's Identit…Extended Euclide…Modular Mu…

A modular multiplicative inverse of an integer aa modulo an integer n>1n>1 is an integer bb such that

ab≡1(modn).ab\equiv 1\pmod n.

Equivalently, nn divides ab−1ab-1. Such an inverse exists exactly when aa and nn are relatively prime, meaning that their greatest common divisor is 1. When it exists, the inverse is unique modulo nn and is commonly written a−1(modn)a^{-1}\pmod n. Modular inverses make division possible in modular arithmetic and are fundamental to computational number theory and cryptography.

Definition and examples

For example,

3⋅5=15≡1(mod7),3\cdot 5=15\equiv 1\pmod 7,

so 5 is an inverse of 3 modulo 7. Every integer congruent to 5 modulo 7, such as −2-2, 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 0,1,…,n−10,1,\ldots,n-1.

By contrast, 2 has no inverse modulo 6. Every product 2b2b is even, whereas every integer congruent to 1 modulo 6 is odd.

The notation a−1a^{-1} in this setting does not generally denote the ordinary reciprocal 1/a1/a 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

a is invertible modulo n⟺gcd⁡(a,n)=1.a \text{ is invertible modulo }n \quad\Longleftrightarrow\quad \gcd(a,n)=1.

If bb is an inverse, then ab≡1(modn)ab\equiv1\pmod n, so there is an integer kk such that

ab−kn=1.ab-kn=1.

Any common divisor of aa and nn must therefore divide 1, proving that their greatest common divisor is 1.

Conversely, Bézout’s identity states that if gcd⁡(a,n)=1\gcd(a,n)=1, there are integers xx and yy satisfying

ax+ny=1.ax+ny=1.

Reducing this equation modulo nn gives ax≡1(modn)ax\equiv1\pmod n, so xx is an inverse.

For uniqueness, suppose ab≡1(modn)ab\equiv1\pmod n and ac≡1(modn)ac\equiv1\pmod n. Multiplying the second congruence by bb and using ba≡1(modn)ba\equiv1\pmod n gives c≡b(modn)c\equiv b\pmod n.

These statements concern multiplicative inverses. Every residue has an additive inverse, namely −a(modn)-a\pmod n, 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 x,yx,y such that

ax+ny=gcd⁡(a,n).ax+ny=\gcd(a,n).

If the greatest common divisor is 1, the coefficient xx, reduced modulo nn, is the required inverse. Otherwise, no inverse exists.

For example, to invert 17 modulo 43:

43=2⋅17+9,17=1⋅9+8,9=1⋅8+1.\begin{aligned} 43&=2\cdot17+9,\\ 17&=1\cdot9+8,\\ 9&=1\cdot8+1. \end{aligned}

Back-substitution gives

1=9−8=2⋅9−17=2⋅43−5⋅17.\begin{aligned} 1&=9-8\\ &=2\cdot9-17\\ &=2\cdot43-5\cdot17. \end{aligned}

Hence

17−1≡−5≡38(mod43).17^{-1}\equiv-5\equiv38\pmod{43}.

After reducing aa modulo nn, the algorithm takes O(log⁡n)O(\log n) 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 pp, Fermat’s little theorem gives

ap−1≡1(modp)a^{p-1}\equiv1\pmod p

whenever pp does not divide aa. Therefore,

a−1≡ap−2(modp).a^{-1}\equiv a^{p-2}\pmod p.

For p=2p=2, the only nonzero residue is 1, which is its own inverse.

More generally, Euler’s theorem gives

aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod n

when gcd⁡(a,n)=1\gcd(a,n)=1, where Euler’s totient function φ(n)\varphi(n) counts the invertible residue classes modulo nn. Consequently,

a−1≡aφ(n)−1(modn).a^{-1}\equiv a^{\varphi(n)-1}\pmod n.

Repeated squaring computes these powers efficiently. For a general composite modulus, however, finding φ(n)\varphi(n) may require information not already available, such as a factorization of nn. 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

ax≡1(modpk),ax\equiv1\pmod{p^k},

define

x′=x(2−ax).x'=x(2-ax).

Then

1−ax′=(1−ax)2,1-ax'=(1-ax)^2,

so

ax′≡1(modp2k).ax'\equiv1\pmod{p^{2k}}.

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 aa is invertible modulo nn, the congruence

ax≡b(modn)ax\equiv b\pmod n

has the unique solution

x≡a−1b(modn).x\equiv a^{-1}b\pmod n.

This is the modular counterpart of dividing both sides of an equation by aa.

Without an inverse, division cannot be performed in this way. Nevertheless, the congruence may still have solutions. Let d=gcd⁡(a,n)d=\gcd(a,n). Then:

  • If dd does not divide bb, there are no solutions.
  • If dd divides bb, there are exactly dd distinct solutions modulo nn.

In the second case, dividing the integer coefficients and modulus by dd gives

adx≡bd(modn/d),\frac{a}{d}x\equiv\frac{b}{d}\pmod{n/d},

whose coefficient is invertible modulo n/dn/d.

For example,

6x≡8(mod14)6x\equiv8\pmod{14}

reduces to

3x≡4(mod7).3x\equiv4\pmod7.

Since 3−1≡5(mod7)3^{-1}\equiv5\pmod7, this gives x≡6(mod7)x\equiv6\pmod7, corresponding to the two solutions x≡6x\equiv6 and x≡13(mod14)x\equiv13\pmod{14}.

This distinction also governs cancellation: cancelling a factor that is not invertible generally requires changing the modulus.

Algebraic interpretation

The residue classes modulo nn form the ring Z/nZ\mathbb Z/n\mathbb Z. Its invertible elements are called units. Under multiplication they form an abelian group, written

(Z/nZ)×,(\mathbb Z/n\mathbb Z)^\times,

with φ(n)\varphi(n) elements.

If n=pn=p is prime, every nonzero residue is invertible, and Z/pZ\mathbb Z/p\mathbb Z is a finite field. If nn is composite, some nonzero residues are not invertible. Such residues are zero divisors: if d=gcd⁡(a,n)>1d=\gcd(a,n)>1 and a≢0(modn)a\not\equiv0\pmod n, then the nonzero residue n/dn/d satisfies

a(n/d)≡0(modn).a(n/d)\equiv0\pmod n.

The Chinese remainder theorem gives a componentwise description. If n=rsn=rs with gcd⁡(r,s)=1\gcd(r,s)=1, then aa is invertible modulo nn exactly when it is invertible modulo both rr and ss. Its inverse modulo nn 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 Z/nZ\mathbb Z/n\mathbb Z is invertible exactly when its determinant is a unit. For an integer matrix AA, this means gcd⁡(det⁡A,n)=1\gcd(\det A,n)=1.
  • 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.