-2
$\begingroup$

I need to find $(a/b) \bmod m$ where
$m= 500000002$
(hence $m = 148721 \times 41 \times 41 \times 2\qquad\text{(prime factorization)}$ basically I need to find $a_n\binom{2n}{n}$, which satisfies the recursion $a_n = a_{n-1} \times\left(\frac{4n-2}{n}\right).$

I am using Chinese remainder theorem to solve but unable to get the correct answer.

Can someone help??

  • 0
    possible duplicate of [${n \choose k} \bmod m$ using Chinese remainder theorem?](http://math.stackexchange.com/questions/95491/n-choose-k-bmod-m-using-chinese-remainder-theorem) and [this](http://math.stackexchange.com/questions/173291/).2012-07-20

3 Answers 3

1

I don't think you can think of (a/b) mod m in general when m is not prime, as inverse of b mod m will not be defined unless b is coprime to m (eg. here what if b is 2? What then is (1/2) mod m?). You are better off finding the answer modulo each prime factor and then combining the result using the chinese remainder theorem.

  • 0
    Well basically you have to keep in mind that 2nCn is ultimately an integer say x. Once you have got its value mod say p1 and p2, you can get it mod p1 * p2.2012-07-18
1

i have the value value (2n)! and n!....what i have to calculate is 2nCn and i have the value of MOD=10^9+7....now the problem is if i am using chinese remaider theorem.... i am using recurrence x= 1 mod 2 and x= exp mod 500000003....where exp is 2nCn...since n can be great as 10^5....i am not getting how to use CRT to calculate exp..?

0

If I understand well you need to find

$\binom{2n}{n} \mod m \,,$

where $m=500000002$.

Note that $\binom{2n}{n}$ are integers, so there is no problem with their definition. Anyhow, your approach is WRONG, as in your recursive definition you need sometime to divide by $0 \mod m$.

I would recommend you the following approach:

For each prime $p$ find first if $p | \binom{2n}{n}$ by using the formula for power of prime in a factorial. Then, if the answer is negative, cancel first $p^k$ in $\frac{(2n)!}{n! n!}$ and then try using Wilson theorem to calculate what is leftm namely $\frac{(2n)!}{p^a}$ and $\frac{(n)!}{p^b}$ modulo $p$. The prime $148721$ is a tough one though.

Alternately, if you try using your recurrence, note that the recurrence formula only works when $p \nmid n$. If $p |n$ you are dividing by 0, which probably explains the wrong answer, you need to calculate $a_n$ by a different method in this case.

P.S. Do you need to calculate it for ALL n or just some of them?

  • 0
    I need to calcluate till n=10^5 ..btw thnks for our help I will try and implement this and tell you the results later ..thanks2012-07-19