# $a/b\bmod{m}$ when $m$ is not a prime

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

-
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. –  joriki Jul 18 '12 at 10:55
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. –  Gerry Myerson Jul 18 '12 at 12:33
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.. –  user1489938 Jul 18 '12 at 12:38
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. –  Graphth Jul 18 '12 at 17:52
possible duplicate of ${n \choose k} \bmod m$ using Chinese remainder theorem? and this. –  Quixotic Jul 20 '12 at 21:18

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.

-
OP is using the Chinese Remainder Theorem, according to the question. –  Gerry Myerson Jul 18 '12 at 12:34
but how to combine the result when their is a denominator involved??? –  user1489938 Jul 18 '12 at 12:40
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. –  Wonder Jul 18 '12 at 15:22

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

-

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?

-
No, he said he wants to find $a_n \binom{2n}{n} \mod m$ and he defines what $a_n$ is... except he didn't tell us $a_1$. –  Graphth Jul 18 '12 at 17:53
He probably mean $a_n=\binom{2n}{n}$. Note that $\binom{2n}{n}=\frac{4n-2}{n} \binom{2(n-1)}{n-1}$. –  N. S. Jul 18 '12 at 18:06
Good point, that makes sense... just a missing = makes things confusing. Good work on decrypting that message. –  Graphth Jul 18 '12 at 18:10
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 ..thanks –  user1489938 Jul 19 '12 at 4:03