http://code.activestate.com/recipes/tags/modulo/popular/2013-01-31T23:41:21-08:00ActiveState Code Recipes2013-01-31T23:41:21-08:00Justin Shawhttp://code.activestate.com/recipes/users/1523109/http://code.activestate.com/recipes/576737-inverse-modulo-p/

<p style="color: grey"> Python recipe 576737 by <a href="/recipes/users/1523109/">Justin Shaw</a> (<a href="/recipes/tags/mod/">mod</a>, <a href="/recipes/tags/modulo/">modulo</a>, <a href="/recipes/tags/number/">number</a>, <a href="/recipes/tags/prime/">prime</a>, <a href="/recipes/tags/theory/">theory</a>). Revision 4. </p> <p>Very rarely it is necessary to find the multiplicative inverse of a number in the ring of integers modulo p. Thie recipe handles those rare cases. That is, given x, an integer, and p the modulus, we seek a integer x^-1 such that x * x^-1 = 1 mod p. For example 38 is the inverse of 8 modulo 101 since 38 * 8 = 304 = 1 mod 101. The inverse only exists when a and p are relatively prime.</p>