Modular Inverse

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, .

REFERENCES:

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