I want to calculate nCr (mod $10^9+1)$.so for calculating nCr we have:
$$nCr=\frac{n!}{r!(n-r)!}$$
so I want to know whether it is true that I perform modulo operator to numerator and denominator separately instead of perform it to the result of nCr fraction directly?
I mean if it is true I can calculate the result like this:
$${nCr} \pmod {10^9+1}=\frac{n! \pmod{10^9+1}}{r!(n-r)! \pmod{10^9+1}}$$
and if it is not true what is the solution because my numbers are very large and I can't perform modulo operator to the final result of the fraction.
Best Answer
Yes, as I explain here (and its links) modular arithmetic is well-defined on all fractions expressible with denominator coprime to the modulus.
So in your example you'll first need to cancel from the denominator all factors in common with your modulus $10^9 + 1 = 7\cdot 11\cdot 13\cdot 19\cdot 52579\ $ (compare this purely arithmetical proof that binomial coefficients are integers).
As an example of problems with denominators not coprime to the modulus consider $ 6 = (2\cdot 6)/2.\,$ Reduced $\!\bmod 10\,$ it yields $\,2/2\,$ so if we naively cancel $2$ then we get the wrong answer $1$ (vs. $6).\,$ The problem is that $2$ is not cancellable $\bmod 10$. In fact $\,2/2\pmod{\!10} = 1\pmod{\!5}\,$ is the solution of $\,2x\equiv 2\pmod{\!10},\,$ so we need to cancel $2$ from the modulus too to obtain the complete set of modular solutions, i.e. this modular "fraction" or division is multi-valued (see here for much more).
But the original division operation in $\,6 = (2\cdot 6)/2\,$ denotes single-valued division in integers, not the prior multi-valued modular division. Generally the two agree only when the divisor is coprime to the modulus. So we need to preprocess the fraction by performing said cancellations (generally if you can't cancel all factors in common with the modulus then the modular fraction doesn't exist). This is explained at length if you chase links starting with the first link above.