-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??

  • 1
    I doubt that the three keystrokes you saved by abbreviating "answer" were worth forcing all the people who read this to briefly think about what that abbreviation means.2012-07-18
  • 2
    Incomprehensible. You say you want to find $a/b$; then you say you want to find 2nCn (does this mean the combinatorial symbol, $2n$-choose-$n$?); then there's something about $a_n$; how are these three things related? Maybe you had best show us in detail your attempt to solve it, and tell us how you know you are not getting the correct answer, and then maybe we'll be able to figure out what you are talking about.2012-07-18
  • 0
    sorry for the inconvience cauused in explaining the terms... the 2nCn here means 2n choose n which is the central binomial coefficient and an and an-1 represent the relation between 2nCn and 2(n-1)C(n-1) ... basically a recursive relation..2012-07-18
  • 0
    Here's the deal. You want to find $a_n \binom{2n}{n} \mod m$, where $a_n$ satisfies the occurrence above, right? But, you said you want to find $a/b \mod m$ which only confuses things. What are $a$ and $b$? I assume you meant, you want to find a fraction mod m, and then below you described what that fraction actually is. Delete out the $a/b$ if that is the case. People can read your definition of $a_n$ and realize it's a fraction. But, more importantly, you haven't told us what $a_1$ is so we have no idea what $a_n$ is so we can't possibly solve this.2012-07-18
  • 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