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.
Number Theory – Using Chinese Remainder Theorem for Binomial Coefficients Modulo m
binomial-coefficientsmodular arithmeticnumber theory
Related Solutions
The CRT basically says says that the natural projection from $\Bbb Z$ onto that product is surjective.
Being surjective, $z\mapsto(0+5\Bbb Z,0+11\Bbb Z,1+7\Bbb Z)$ for some $z\in \Bbb Z$. By an isomorphism theorem, you turn this into a isomorphism from $\Bbb Z/(385)$ to the product. It is still surjective, and since it is injective, this says the answer $z$ is unique (mod $385$).
One naive way to solve this would be to look at multiples of $55$ and see which one is congruent to $1$ mod $7$.
There is a simple algorithm to compute more complex cases. Let's suppose you want a simultaneous solution to get $(a,b,c)$ instead of $(0,0,1)$. Since 77 is coprime to 5, you can find an inverse mod 5, which turns out to be 3. Then $77\cdot3\cdot a\cong a\pmod{5}$, but it is zero mod 7 and mod 11.
Since 35 is coprime with 11, we can find an inverse mod 7, which turns out to be 6.Then $35\cdot 6\cdot b\cong b\pmod{11}$, but it is zero mod 5 and mod 7.
Finally, 55 has an inverse mod 7, namely 6. Thus $6\cdot 55\cdot c\cong c\pmod{7}$, and zero mod 5 and mod 11.
Summing all of these, we get that $77\cdot 3\cdot a+35\cdot 6\cdot b+55\cdot 6\cdot c=z$ is a solution to the simultaneous modular equations. If you need it to be below 385 you can just reduce it mod 385, or if you need it to be some number you can just increase it mod 385 to get the desired number.
It has nothing to do with prime moduli or CRT. Rather, it is true for all moduli $\,n\,$ as we can easily prove as follows, using notation $\ \bar x := x\bmod n\, $ for the remainder left after dividing $\,x\,$ by $\,n.$
Applying the equivalence $\ x\equiv y\pmod{\! n}\!\color{#c00}\iff \bar x = \bar y,\, $ and $\,\small \rm\color{#0a0}{CPR} =$ Congruence Product Rule
$$\begin{align} {\rm mod}\ n\!:\,\ a \,&\color{#c00}\equiv\, \bar a\\ b\,&\color{#c00}\equiv\, \bar b\\ \smash{\overset{\rm\color{#0a0}{CPR}}\Longrightarrow}\,\ \ a\:\!b \,&\equiv\, \bar a\:\!\bar b\\ \color{#c00}\Longrightarrow\ a\:\!b\bmod n \,&=\, \bar a\:\! \bar b\bmod n,\ \ {\rm i.e.}\ \ \overline{ab} = \overline{\bar a \bar b} \end{align}\!\!$$
Remark $ $ Generally, as above, to prove an identity about mod as an operator it is usually easiest to first convert it into the more flexible congruence form, using $\color{#c00}\Longleftarrow$ in the equivalence, then prove it using congruences, then at the end, convert it back to operator form, using $\color{#c00}\Longrightarrow$ in the equivalence.
For a similar example consider equivalence of fractions, $\,\frac{a}b \equiv \frac{c}d\iff ad = bc.\,$ It would be quite cumbersome to do fraction arithmetic if we required that all fractions always be in normal (reduced) form, i.e. in least terms. Instead, it proves more convenient to have the flexibility to work with arbitrary equivalent fractions. For example, this allows us to state the fraction addition rule in very simple form by first choosing convenient reps having a common denominator.
See here for further discussion on $\!\bmod\!$ as a binary operator vs. equivalence relation.
See here for how to interpret the above as transporting the ring operations on cosets in the quotient ring $\,\Bbb Z/n\,$ to corresponding operations on their normal-form (remainder) reps in $\,\Bbb Z_n$.
Best Answer
Andrew Granville's paper Binomial coefficients modulo a prime power (you can find a copy here) has the following generalization of Lucas' Theorem:
Granville then writes:
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).