Calcluating division mod a prime 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?
 A: It looks like your question boils down to: when can I divide an expression while reducing it $\pmod m$? Take this example:
\begin{align*}
    (8/2) \pmod 6 &\equiv \frac{8 \pmod 6}{2\pmod 6}\\
    &\equiv \frac{2 \pmod 6}{2\pmod 6}\\
    &\equiv 1\pmod 6\\
    4\pmod 6 &\equiv 4 \pmod 6.
\end{align*}
So, in general we know that
$$
\frac{a}{b}\pmod m \neq \frac{a \pmod m}{b \pmod m}.
$$
However as you pointed out, when $m$ is prime, we can divide without worrying about the above problem.
We summarize these findings in the following statement:

When $n$ is a prime number, it is valid to divide by any non-zero number - that is, for each $a \in\{1,2, \ldots, n-1\}$ there is one, and only one, number $u \in\{1,2, \ldots, n-1\}$ such that
$$au = 1 \quad(\bmod n) .
$$
Then, dividing by $a$ is the same as multiplying by $u$, i.e. division by $a$ is given by the rule
$$\frac{b}{a}=b u \quad(\bmod n) .
$$
For example, in mod $7$ , we have
$$\frac{1}{1}=1, \quad \frac{1}{2}=4, \quad \frac{1}{3}=5, \quad \frac{1}{4}=2, \quad \frac{1}{5}=3, \quad \frac{1}{6}=6.
$$

In your example, because $Q$ is prime we can solve the equation as you expressed.
