# ${n \choose k} \bmod m$ using Chinese remainder theorem?

I don't really see too many sites explaining how this is done. Does anyone know how this works? I'm trying to find $\binom{n}{k}\bmod m$, where $n$ and $k$ are large and $m$ is not prime. I think it can be done with the Chinese remainder theorem, but I don't understand how it is all put together.

-
For nice images, see jwilson.coe.uga.edu/emat6680/parsons/mvp6690/essay1/… – lhf Dec 31 '11 at 20:29
Not sure how this is relevant – WhatsInAName Dec 31 '11 at 20:31
$1$) Factor $m$ (this may be expensive) as $\prod p_i^{e_i}$. $2$) For each $p_i^{e_i}$, find $a_i$ such that $\binom{n}{k}\equiv a_i \pmod{p_i^{e_i}}$. Andrew Granville gives an algorithm for finding $a_i$ in a paper referenced in the Wikipedia article. $3$) Solve the system of congruences $x\equiv a_i\pmod{p_i^{e_i}}$. A procedure for this is given in the Wikipedia CRT article. As given, it involves unnecessarily large numbers. $4$) Reduce $x$ modulo $m$. It is conceivable there are good algorithms that don't involve factoring $m$, CRT. – André Nicolas Dec 31 '11 at 21:51
The proof of the CRT is usually given constructively: it tells you exactly how to find the value modulo $21$ if you know the value modulo $3$ and the value modulo $7$. If $x\equiv a\pmod{3}$ and $x\equiv b\pmod{7}$, then let $A$ be a number that is $1$ modulo $3$ and $0$ modulo $7$ (e.g., $A=7$); and let $B$ be a number that is $1$ modulo $7$ and $0$ modulo $3$ (e.g., $B=15$). Then $x = Aa + Bb$ is the unique number (modulo 21) that has $x\equiv a\pmod{3}$ and $x\equiv b\pmod{7}$. – Arturo Magidin Dec 31 '11 at 22:00
@user1123950: Finding $\binom{n}{k}$ modulo $m$ is the same as finding $\binom{n}{k}$ modulo $p^r$ for all $p$ that are prime factors of $m$, where $r$ is the largest integer such that $p^r$ divides $m$. The primes that divide $m$ are not enough, you need the largest prime powers that divide $m$. That means that for squarefree $m$, Lucas' Theorem and the CRT are enough, but for non-squarefree $m$, you need the generalization of Lucas' Theorem given below and the CRT. – Arturo Magidin Dec 31 '11 at 23:22

Andrew Granville's paper Binomial coefficients modulo a prime power (you can find a copy here) has the following generalization of Lucas' Theorem:

Theorem. Let $p^q$ be a prime power, and let $n=k+r$ be given. Write $$k = k_0 + k_1p + \cdots + k_dp^d$$ in base $p$, and let $K_j$ be the least positive positive residue of $\left\lfloor \frac{k}{p^j}\right\rfloor\pmod{p^q}$ for each $j\geq 0$, so that $$K_j = k_j + k_{j+1}p + \cdots + k_{j+q-1}p^{q-1};$$ make the same definitions for $n_j$, $N_j$, $r_j$, and $R_j$. Let $e_j$ be the number of indices $i\geq j$ for which $n_i\leq k_i$ (the number of "carries" when adding $k$ and $r$ in base $p$ at or beyond the $j$th digit). Then $$\frac{1}{p^{e_0}}\binom{n}{k} \equiv (\pm 1)^{e_{q-1}}\left(\frac{(N_0!)_p}{(K_0!)_p(R_0!)_p}\right)\left(\frac{(N_1!)_p}{(K_1!)_p(R_1!)_p}\right)\cdots\left(\frac{(N_d!)_p}{(K_d!)_p(R_d!)_p}\right)\pmod{p^q},$$ where $(\pm 1)$ is $-1$ except when $p=2$ and $q\geq 3$, and $(s!)_p$ is the product of the positive integers less than or equal to $s$ that are not divisible by $p$.

Granville then writes:

[This] Theorem[] provides a quick way to compute the value of the binomial coefficients modulo arbitrary prime powers, as it is straightforward to determine each of the $n_j$, $N_j$, $e_j$, etc. and then one need only determine the value of $(s!)_p\pmod{p^q}$ with $k\lt p^q$[.]

Once you have the value modulo prime powers, the Chinese Remainder Theorem (whose proof is almost invariably given constructively in textbooks) tells you how to find the value modulo $m$.

In the special case where $q=1$, the Theorem yields Lucas' Theorem: if $n_0$ and $m_0$ are the least nonnegative remainders of $n$ and $m$ modulo $p$, then $$\binom{n}{m} \equiv \binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\binom{n_0}{m_0}\pmod{p},$$ if we interpret $\binom{r}{s}=0$ when $r\lt s$.

How does the CRT put the information together? This is found in pretty much all textbooks of Elementary Number Theory that I am familiar with:

Suppose you know that $x=\binom{n}{k}$ satisfies congruences \begin{align*} x&\equiv a_1\pmod{m_1}\\ x&\equiv a_2\pmod{m_2}\\ &\vdots\\ x&\equiv a_r\pmod{m_r} \end{align*} where $m_1,\ldots,m_r$ are pairwise coprime (e.g., pairwise distinct primes, or prime powers of pairwise distinct primes, or any other collection of integers that are pairwise coprime), and $a_1,\ldots,a_r$ are arbitrary integers.

The Chinese Remainder Theorem says that there is a unique value of $x\bmod {m_1\times\cdots\times m_r}$ that satisfies all these congruences simultaneously.

The algorithmic method that appears in most textbooks is the following: for each $i=1,\ldots,r$, let $$M_i = \frac{m_1\times\cdots\times m_r}{m_i}.$$ That is, the product of all moduli except for the $i$th one. Then $\gcd(m_i,M_i)=1$, so we can find (e.g., by the Extended Euclidean Algorithm) integers $s_i$ and $t_i$ such that $$1 = s_iM_i + t_im_i.$$ Do this for each $i$. Then let $x$ be the remainder modulo $m_1\times\cdots\times m_r$ of $$a_1s_1M_1 + a_2s_2M_2 + \cdots +a_rs_rM_r.$$ Then $x$ satisfies all the original congruences and is the unique integer modulo $m_1\times\cdots\times m_r$ that satisfies the original congruences: since $M_i\equiv 0\pmod{m_j}$ if $i\neq j$ and $s_iM_i\equiv 1\pmod{m_i}$, we have that $$a_1s_1M_1+\cdots + a_rs_rM_r \equiv a_is_iM_i \equiv a_i\pmod{m_i}\quad\text{for each }i=1,2,\ldots,r.$$

For example: take $B=\binom{456}{51}$, $m=30 = 2\times 3\times 5$.

We find $B\bmod 2$, $B\bmod 3$, and $B\bmod 5$, e.g. using Lucas' Theorem. \begin{align*} 456 &= 0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3 + 0\times 2^4 + 0\times 2^5 + 1\times 2^6 + 1\times 2^7 + 1\times 2^8\\ &= 0 + 2\times 3^1 + 2\times 3^2 + 1\times 3^3 + 2\times 3^4 + 1\times 3^5\\ &= 1 + 1\times 5 + 3\times 5^2 + 3\times 5^3\\ 51 &= 1 + 1\times 2 + 0\times 2^2 + 0\times 2^3 + 1\times 2^4 + 1\times 2^5\\ &= 0 + 2\times 3 + 2\times 3^2 + 1\times 3^3\\ &= 1 + 0\times 5 + 2\times 5^2 \end{align*} So \begin{align*} \binom{456}{51} &\equiv \binom{0}{1}\binom{0}{1}\binom{0}{0}\binom{1}{0}\binom{0}{1}\binom{0}{1}\binom{1}{0}\binom{1}{0}\binom{1}{0}\pmod{2}\\ &\equiv 0\pmod{2}\\ \binom{456}{51}&\equiv \binom{0}{0}\binom{2}{2}\binom{2}{2}\binom{1}{1}\binom{2}{0}\binom{1}{0}\pmod{3}\\ &= 1\pmod{3}\\ \binom{456}{51} &\equiv \binom{1}{1}\binom{1}{0}\binom{3}{2}\binom{3}{0}\pmod{5}\\ &=3\pmod{3}. \end{align*} So we are trying to find the value of $x$ modulo $30$ such that \begin{align*} x&\equiv 0\pmod{2}\\ x&\equiv 1\pmod{3}\\ x&\equiv 3\pmod{5}. \end{align*} We have $M_1 = 15$, $M_2 = 10$, $M_3 = 6$. We can write $$1=M_1 -7m_1,\quad 1 = M_2-3m_2,\quad 1=M_3-m_3.$$ So the number we want is $x=0M_1 + 1M_2 + 3M_3 = 10+18 = 28\bmod{30}$.

Hence $\binom{456}{31}\equiv 28\pmod{30}$.

Note. There are nicer ways of solving the problem of combining the congruences into a single congruence modulo $m_1\cdots m_r$ if you are working with pencil-and-paper; they can probably be programmed into a computer as well. Suppose we are trying to find the unique $x$ modulo $30$ such that $x\equiv 0\pmod{2}$, $x\equiv 1\pmod{3}$, and $x\equiv 3\pmod{5}$. From the first congruence, we know that $x=2a$ for some $a$. Plugging into the second congruence, we have $2a\equiv 1\pmod{3}$. Since $2\equiv -1\pmod{3}$, we have $-a\equiv 1\pmod{3}$, or $a\equiv 2\pmod{3}$; hence, $a=2+3b$. Plugging into $x=2a$ we have $x=4+6b$. Plugging this into the third congruence we have $4+6b\equiv 3\pmod{5}$, or $b\equiv -1\equiv 4\pmod{5}$. So $b=4+5c$. Plugging into the formula for $x$ we get $$x = 2a = 2(2+3b) = 4+6b = 4+6(4+5c) = 4+24+30c = 28+30c,$$ that is, $x\equiv 28\pmod{30}$, same answer as before.

Note 2. In particular, Lucas' Theorem tells you how to compute $\binom{n}{k}\bmod p$ for primes $p$. With Lucas' Theorem and the Chinese Remainder Theorem, you can compute $\binom{n}{k}\bmod m$ for any squarefree integer $m$ (exactly what Qiaochu said in his comment way back when). In order to compute $\binom{n}{k}\bmod m$ for arbitrary integers $m$, first you need to factor $m$ into prime powers, $$m = p_1^{\alpha_1}\cdots p_r^{\alpha_r},$$ where $p_1,\ldots,p_r$ are pairwise distinct primes and $a_i\gt 0$ for each $i$; then solve $\binom{n}{k}\bmod{p_i^{\alpha_i}}$ for each $i$ (that is, compute the remainder modulo the prime powers; this can be done using Granville's generalization of Lucas' theorem given above); and then using the Chinese Remainder Theorem to combine all the congruences $\binom{n}{k}\equiv a_i\pmod{p_i^{\alpha_i}}$ into a single congruence modulo $p_1^{\alpha_1}\cdots p_r^{\alpha_r}= m$ (exactly what André Nicolas said in his comment).

-
I already have a method for finding modulo p -- I just have no clue how to automatically find modulo m – WhatsInAName Dec 31 '11 at 22:26
@user1123950: What does "automatically" mean? The theorem above gives you an algorithm for solving the problem modulo prime powers. The Chinese Remainder Theorem gives you and algorithm for combining the solutions to a remainder modulo $m$. – Arturo Magidin Dec 31 '11 at 22:29
@user1123950: As to "never seeing hard examples," the point being made repeatedly is that the hard part of the problem you originally asked had nothing to do with the Chinese Remainder Theorem. The hard part is figuring out those binomial coefficients mod powers of primes. Once you've done this, as in your 456 example above, it's exactly the same very routine Chinese remainder theorem explanation you've likely found everywhere else. So by attempting to make it harder, you've forced Arturo to do a lot more work than necessary! (So a big +1 to him!) – Cam McLeman Dec 31 '11 at 23:29
@Arturo: Thanks for the reference to Granville's theorem! I had found something similar, but not as complete; this algorithm will be very useful to me. – Jonas Kibelbek Jan 1 '12 at 1:08
@user1123950: My advice: Start a new question. Your real question is how to use the CRT to solve a system of congruences with coprime moduli, and how to use the Euclidean Algorithm to find the integers $s_i$ and $t_i$ such that $1 = s_iM_i + t_im_i$. – Arturo Magidin Jan 1 '12 at 1:41