A modular inverse of an integer 
(modulo 
) is the integer 
such that
 |
A modular inverse can be computed in the Wolfram Language using PowerMod[b, -1, m].
Every nonzero integer 
has an inverse (modulo 
)
for 
a prime and 
not a multiple of 
.
For example, the modular inverses of 1, 2, 3, and 4 (mod 5) are 1, 3, 2, and 4.
If 
is not prime, then not every nonzero integer 
has a modular inverse. In fact, a nonzero integer 
has a modular inverse modulo 
iff 
and 
are relatively prime.
For example, 
(mod 4) and 
(mod 4), but 2 does not have a modular inverse.
 |
The triangle above (OEIS A102057) gives modular inverses of 
(mod 
)
for 
,
2, ..., 
and 
,
3, .... 0 indicates that no modular inverse exists.
If 
and 
are relatively prime, there exist integers 
and 
such that 
, and such integers may be found using the Euclidean
algorithm. Considering this equation modulo 
, it follows that 
; i.e., 
.
If 
and 
are relatively prime, then Euler's totient theorem
states that 
,
where 
is the totient function. Hence, 
.
