0
$\begingroup$

I am unfamiliar with number theory but am trying to calculate the following for a coding challenge:

$$\frac{(N-M-1)!}{N!(M-1)!}\pmod{Q}$$

where $Q$ is prime. I know that I can calculate the "modular" factorial fairly easily:

$$(N-M-1)!\bmod{Q} \equiv (((N-M-1)\times (N-M-2))\bmod{Q} \times \dots))\bmod{Q}$$

However, I'm not sure how I calculate the division part, I know that we can rewrite the fraction:

$$\frac{(N+M-1)!}{N!(M-1)!}\equiv (N+M-1)!\cdot (N!(M-1)!)^{-1}\pmod{Q}$$

However, can I compute the "modular" factorial of $N$ and $(M-1)$ in the same way and then compute the Modular Inverse of their product, or is there something else I need to do?

$\endgroup$
  • $\begingroup$ Is $Q$ prime? $\,$ $\endgroup$ – Travis Feb 3 '15 at 12:59
  • $\begingroup$ @Travis I've updated the question $\endgroup$ – Thomas Russell Feb 3 '15 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.