I've been doing a programming (coding) exercise, where I'm implementing a method to calculate the remainder of $\frac{a!}{b!}$ divided by a prime number $p$. $a$ and $b$ are any integers between 1 and 1000 inclusive, while $p$ is the prime number $10^9+7$.
Since $a!$ and $b!$ can get very big, it's not possible to calculate these directly in an efficient way. Instead. The idea is to use Fermat's last theorem to simplify as follows:
If $b!$ is not a multiple of $p$, then by Fermat's Little Theorem:
$(b!)^{p-1} \equiv 1 \mod p$
Now divide each side by $b!$ which yields
$(b!)^{p-2} \equiv \frac{1}{b!} \mod p$
Now the original problems becomes (after substitution of $\frac{1}{b!} \mod p$):
$\frac{a!}{b!} \mod p \equiv a! \times (b!)^{p-2} \mod p$
The expression $a! \times (b!)^{p-2} \mod p$ can be fairly easily implemented given specific integers $a$, $b$, and $p$ by repeatedly applying $x \times y \mod p \equiv (x \mod p)(y \mod p) \mod p$ and modular exponentiation algorithm. https://en.wikipedia.org/wiki/Modular_exponentiation
I have two problems with the math behind this solution. Can someone help me understand two things?
1) How is it valid that $\frac{a!}{b!}$ and then dividing it by $p$ to get its remainder is equivalent to the expression $\frac{a!}{b!} \mod p$ ? Best I can tell, modular division states that
Calculating $\frac{a!}{b!} \mod p$ means finding an integer $c$ such as $b! \times c \equiv a! \mod p$. Is it necessarily true so long as $\frac{a!}{b!}$ is an integer, then the reminder of $\frac{a!}{b!}$ when divided by $p$ is the same as finding the integer $c$? It feels like there a bit of abuse of notation here that is kind of magical.
2) Fermat's Little Theorem is only valid if $b!$ is not a multiple of $p$. When is this true? Is the true that for every integer $b$ and every prime number $p$, $b!$ is guaranteed not to be a multiple of $p$?
For a < b, a!/b! is not an integer. Question aborts.
For a = b, a!/b! = 1. The remainder is 1.
For b < a, a!/b! = (b + 1)(b + 2)...a.
If p < a - b, the remainder is 0.
Otherwise use xy mod p = (x mod p)(x mod p) mod p
multiple times.