title: How to calculate "modular multiplicative inverse" when the denominator is not co-prime with m?
body: <p>I need to calculate <strong><code>(a/b) mod m</code></strong> where <strong><code>a</code></strong> and <strong><code>b</code></strong> are very large numbers.</p>
  
  <p>What I am trying to do is to calculate <strong><code>(a mod m) * (x mod m)</code></strong>, where <strong><code>x</code></strong> is the <a href="http://en.wikipedia.org/wiki/Modular_multiplicative_inverse" rel="noreferrer">modular inverse</a> of <strong><code>b</code></strong>.</p>
  
  <p>I tried using <a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm" rel="noreferrer">Extended Euclidean algorithm</a>, but what to do when b and m are not co-prime?
  It is specifically <a href="http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation" rel="noreferrer">mentioned</a> that b and m need to be co-prime.</p>
  
  <p>I tried using the code <a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Formal_description_of_the_algorithm" rel="noreferrer">here</a>, and realized that for example:
  <strong><code>3 * x mod 12</code></strong> is not at all possible for any value of <strong><code>x</code></strong>, it does not exist!</p>
  
  <p><strong>What should I do?</strong> Can the algorithm be modified somehow?</p>