title: Modular Divison when no Modular Multiplicative Inverse exists
body: <p>I'm trying to solve the equation:</p>
  
  <pre><code>(binomial(n - 3, k, p) * binomial(n + k, n - 1, p) / (n + k)) % 1000003
  </code></pre>
  
  <p>My current solution:</p>
  
  <pre><code>int a, b, r;
  a = BinomialModPrime(n - 3, k, P);
  b = BinomialModPrime(n + k, n - 1, P);
  r = ModularMultiply(a, b, P);
  r = ModularMultiply(r, ModularInverse(n + k, P), P);
  </code></pre>
  
  <p>was working fine until I got to a problem set where there was no modular inverse for any (n + k) because </p>
  
  <pre><code>(n + k) % 1000003 == 0.
  </code></pre>
  
  <p>So my question is, is there another way to solve this that doesn't involve multiplication by the modular inverse? For instance, will any of <a href="http://www.math.harvard.edu/~sarah/magic/topics/division" rel="nofollow">these</a> suggestions work for my problem?</p>