title: Modular multiplicative inverse function in Python
body: <p>Does some standard Python module contain a function to compute <a href="http://en.wikipedia.org/wiki/Modular_multiplicative_inverse" rel="noreferrer">modular multiplicative inverse</a> of a number, i.e. a number <code>y = invmod(x, p)</code> such that <code>x*y == 1 (mod p)</code>? Google doesn't seem to give any good hints on this.</p>
  
  <p>Of course, one can come up with home-brewed 10-liner of <a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm" rel="noreferrer">extended Euclidean algorithm</a>, but why reinvent the wheel.</p>
  
  <p>For example, Java's <code>BigInteger</code> has <code>modInverse</code> method. Doesn't Python have something similar?</p>