1
$\begingroup$

How to calculate the value of below expression where $M$ is 1000000007 (prime) and $N$ can be any large number $\le 1000$?

\[\frac{N!}{(N/2)!(N/2)!} \mathbin{\%} M\]

It is possible to simplify it like \[\frac{(N/2 + 1)(N/2 + 2)\cdots N}{(N/2)!}\] but then $(N/2)!$ is still a huge number to calculate.

Now can also simply it further like (n/2 + 1)*(n/2 + 2)...*(n-1)/3*4...(n/2-1). But this still isn't enough.

Is it possible to break it down further?

$\endgroup$
3
  • $\begingroup$ Your question is ambiguous. The simplest way to calculate factorial is the way you stated above. This is obviously from an algorithm problem that tackles the overflow of the factorial function. But to attract good responses to your question, you need to explain what you want exactly. $\endgroup$
    – user31280
    Feb 6, 2013 at 20:44
  • $\begingroup$ this is actually in reference to quesion stackoverflow.com/questions/14736514/… and this is an algorithm problem. $\endgroup$
    – g4ur4v
    Feb 6, 2013 at 20:47
  • 1
    $\begingroup$ could you include the reference in your question? $\endgroup$
    – user31280
    Feb 6, 2013 at 20:54

1 Answer 1

2
$\begingroup$

What is needed here is Modular Multiplicative Inverse i.e. $x$ i sthe multiplicative inverse of a iff $$ax \equiv aa^{-1} \equiv 1 \mod m$$ The multiplicative inverse of $a$ modulo $m$ exists if and only if $a$ and $m$ are coprime, so if $m$ is prime then every number that is not a multiple of $m$ has a multiplicative inverse modulo $m$.

To solve the problem $ax \equiv 1 \mod m \implies ax-mk=1| k\in \mathbb Z$, since our problem satisfies Bézout's Identity ($a$ and $m$ are coprime.) one can apply Extended Euclidean Algorithm. You can find the algorithm in Python code here.

To compute $\cfrac {n!}{a!\times b!}$ modulo $m$, you can rewrite this as $n!\times(a!)^{-1}\times(b!)^{-1}$. As long as none of $a,\ b,\ $or $n$ is greater $m$, then there shouldn't be a problem at all.

$\endgroup$
1
  • 1
    $\begingroup$ And if any of $a,b,n$ are greater than $m$, Lucas's theorem applies since $m$ is prime. $\endgroup$
    – Erick Wong
    Feb 7, 2013 at 0:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .