TOPICS
Search

Modular Inverse


A modular inverse of an integer b (modulo m) is the integer b^(-1) such that

 bb^(-1)=1 (mod m).

A modular inverse can be computed in the Wolfram Language using PowerMod[b, -1, m].

Every nonzero integer b has an inverse (modulo p) for p a prime and b not a multiple of p. For example, the modular inverses of 1, 2, 3, and 4 (mod 5) are 1, 3, 2, and 4.

If m is not prime, then not every nonzero integer b has a modular inverse. In fact, a nonzero integer b has a modular inverse modulo m iff b and m are relatively prime. For example, 1^(-1)=1 (mod 4) and 3^(-1)=3 (mod 4), but 2 does not have a modular inverse.

 1 
12 
103 
1324 
10005 
145236

The triangle above (OEIS A102057) gives modular inverses of b (mod m) for b=1, 2, ..., m-1 and m=2, 3, .... 0 indicates that no modular inverse exists.

If b and m are relatively prime, there exist integers x and y such that bx+my=1, and such integers may be found using the Euclidean algorithm. Considering this equation modulo m, it follows that bx=1; i.e., x=b^(-1) (mod m).

If b and m are relatively prime, then Euler's totient theorem states that b^(phi(m))=1 (mod m), where phi(m) is the totient function. Hence, b^(-1)=b^(phi(m)-1) (mod m).


See also

Congruence, Congruence Equation, Linear Congruence Equation

Portions of this entry contributed by Nick Hobson (author's link)

Portions of this entry contributed by Reid Nichol

Explore with Wolfram|Alpha

References

Sloane, N. J. A. Sequence A102057 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Modular Inverse

Cite this as:

Hobson, Nick; Nichol, Reid; and Weisstein, Eric W. "Modular Inverse." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ModularInverse.html

Subject classifications