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.
Answer
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).
No comments:
Post a Comment