5
$\begingroup$

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.

  • 0
    For nice images, see http://jwilson.coe.uga.edu/emat6680/parsons/mvp6690/essay1/sierpinski.html2011-12-31
  • 0
    Not sure how this is relevant2011-12-31
  • 0
    Start with http://en.wikipedia.org/wiki/Lucas'_theorem . This solves the problem for squarefree $m$. In general this seems a little difficult (by CRT the problem reduces to prime powers $m$).2011-12-31
  • 0
    I already checked that page out but was still not sure how to use CRT with the results2011-12-31
  • 2
    $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.2011-12-31
  • 0
    The CRT tells you that the remainder modulo $m$ is completely determined by the remainder modulo the prime powers that divide $m$; that is, factor $m$ into primes, $m=p_1^{a_1}\cdots p_r^{a_r}$, $p_1\lt \cdots \lt p_r$ primes, $a_i\gt 0$; if you know $\binom{n}{k}\bmod p_i^{a_i}$ for each $i$, then you know $\binom{n}{k}\bmod m$. So the problem reduces to the case where $m$ is a prime power.2011-12-31
  • 0
    Can someone provide a simple example? Say I have (456 choose 51) mod 21 (answer is 7) where 3 and 7 are the prime factors of 21. How would I combine (456 choose 51) mod 3 and (456 choose 51) mod 7?2011-12-31
  • 2
    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}$.2011-12-31
  • 0
    How do I know which numbers are 1 mod 3 and 0 mod 7 for instance? Is this just randomly chosen?2011-12-31
  • 0
    @user1123950: You *find them*. Since $\gcd(3,7)=1$, you can find $a$ and $b$ (using, say, the Extended Euclidean Algorithm) such that $3a+7b=1$. Then $7b\equiv 1\pmod{3}$ and $7b\equiv 0\pmod{7}$; and $3a\equiv 1\pmod{7}$ and $3a\equiv 0\pmod{3}$. E.g., $1 = (-2)3 + 1(7)$, so a number that is $1$ modulo $3$ and $0$ modulo $7$ is $1(7) = 7$; and a number that is $0$ modulo $3$ and $1$ modulo $7$ is $(-2)(3) = -6$; adding multiples of $3\times 7$ will not change the residue classes, which is how I got $15=-6+21$.2011-12-31
  • 0
    I guess I am confused because I have no idea where each of these steps is coming from. I might understand what you mean more if I use a triple-prime case. How about the same combinatoric mod 30? It breaks down into mod 2, 3, and 5 cases, with answers 0, 1, and 3, respectively. So you're saying I could do 2a+3b+5c=1 to start, right?2011-12-31
  • 0
    @user1123950: It looks like your *actual* question is about the Chinese Remainder Theorem, and nothing whatsoever to do with binomial coefficients. If $a_1,\ldots,a_n$ are integers, and $m_1,\ldots,m_n$ are pairwise coprime integers, let $M_i = (m_1\cdots m_n)/m_i$ for each $i$. Then let $r_i$, $s_i$ be integers such that $r_im_i + s_iM_i = 1$ (use the Euclidean Algorithm to find them). Then $x=a_1s_1M_1 + \cdots + a_ns_nM_n$ is the unique integer modulo $m_1\cdots m_n$ such that $x\equiv a_i\pmod{m_i}$ for $i=1,\ldots,n$.2011-12-31
  • 0
    I am asking about binomial coefficients. Again I am trying to find n choose k mod m *given the ability to find n choose k mod p*. CRT is the algorithm that puts those results together. That is what I am trying to understand in the context of binomial coefficients as stated in the OP.2011-12-31
  • 0
    For $x\equiv a_1\pmod{2}$, $x\equiv a_2\pmod{3}$, $x\equiv a_3\pmod{5}$: $M_1 = 3\times 5 = 15$; $M_2 = 2\times 5 = 10$; $M_3 = 2\times 3 = 6$. Then $1 = 1M_1 - 7\times 2$; $1=1M_2 - 3(3)$; $1 = 1M_3 - 1(5)$. So the number we want is $a_1M_1 + a_2M_2 + a_3M_3 = 15a_1 + 10a_2 + 6a_3$. E.g., if $a_1=1$, $a_2=2$, $a_3=3$, then you want $x=15+20+18 =53\equiv 23\pmod{2\times3\times 5}$; note that $23\equiv 1\pmod{2}$, $23\equiv 2\pmod{3}$, and $23\equiv 3\pmod{5}$, exactly as desired.2011-12-31
  • 0
    @user1123950: So your question is **not** *about* binomial coefficients, it is *purely* about using the CRT. The *reason* why you want to use the CRT has to do with binomial coefficients, but your *question* does not.2011-12-31
  • 0
    I'll have to look over this a bit -- but when I do (456 choose 51) mod 30 I get 28, not 23.2011-12-31
  • 0
    @user1123950: I did not compute $\binom{456}{51}\bmod{30}$. I found the unique $x$ modulo $30$ that satisfies $x\equiv 1\pmod{2}$, $x\equiv 2\pmod{3}$, and $x\equiv 3\pmod{5}$.2011-12-31
  • 0
    I must admit I am frustrated. I brought up a new example in hopes of understanding how CRT works here but you are talking about a computation that isn't related to the combinatoric I just brought up? I am under the assumption that finding (n choose k) mod m is the same as finding (n choose k) mod p for all prime factors of m and combining these results with CRT. Am I mistaken in this assumption?2011-12-31
  • 1
    @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.2011-12-31

1 Answers 1

20

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

  • 0
    I already have a method for finding modulo p -- I just have no clue how to automatically find modulo m2011-12-31
  • 1
    @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$.2011-12-31
  • 0
    It's just that I know how to find the mod p solutions -- I'm just trying to understand the algorithm for combining solutions.2011-12-31
  • 0
    @user1123950: Look at the proof of the Chinese Remainder Theorem in *any* textbook of elementary number theory; most of them will have examples showing how the proof works. The proof is *algorithmic*. It gives you a *formula* for finding the combined remainder, in terms of numbers that can be found using the Extended Euclidean Algorithm.2011-12-31
  • 0
    Right, but that's the algorithm I made this question about. I'm trying to understand the CRT and how it can be used to find mod m for n choose k given the ability to find n choose k mod p where p is a prime within the prime factorization of m.2011-12-31
  • 0
    @user1123950: The CRT tells you how to combine congruences $x\equiv a_i\pmod{m_i}$, $i=1,\ldots,r$, where $\gcd(m_i,m_j)=1$ if $i\neq j$, into a single remainder modulo $m_1\times\cdots m_n$. If all you know is $\binom{n}{k}\bmod{p_i}$, then the CRT tells you how to find $\binom{n}{k}\bmod{p_1\cdots p_r}$. If $m\neq p_1\cdots p_r$, then the CRT does not help you. (That is, the CRT tells you how to go from modulo a prime to modulo a squarefree integer, not to modulo an *arbitrary* integer). And, again, you seem to be saying that your **only** questions are about the CRT.2011-12-31
  • 0
    Yes, I'd say that's accurate. Sorry if I was not entirely clear -- thanks for being patient with me. I've just looked all over the net and everything I find doesn't seem to make a whole lot of sense (I almost never see hard examples being presented to illustrate how it works)2011-12-31
  • 0
    So M1= prime2*prime3, M2=prime1*prime3, M3=prime1*prime2, I'm with you there. Just have to figure out how you're getting 1 = M1-7m1 and 1 = M2-3m2 and all this sort of thing.2011-12-31
  • 0
    @user1123950: The [Extended Euclidean Algorithm](http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) (when inspection doesn't work) tells you how to find integers $a$ and $b$ such that $\gcd(x,y) = ax+by$. That's what you need here.2011-12-31
  • 3
    @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!)2011-12-31
  • 0
    I didn't mean to make more work for anyone, but I already explicitly stated I had a way to get the mod-p cases. Combining things into mod m cases was what I could not find any information about.2011-12-31
  • 0
    Trying to find how he got 7 with the Extended algo2012-01-01
  • 0
    @user1123950: The expressions for $1$ that I gave were found by inspection; but the usual way would be to divide $15$ by $2$ (quotient $7$, remainder $1$). That means that $15 = 7\times 2 + 1$, or that $1=15-7\times 2$. Exactly what I wrote.2012-01-01
  • 0
    @user1123950: Your original post did not say anything about already knowing how to do it modulo $p$; and in any case, your original post was about **arbitrary** $m$; knowing how to solve modulo primes is insufficient for the general case, with or without the Chinese Remainder Theorem. In your question, the only difficult, non-standard part is figuring out $\binom{n}{k}$ modulo prime **powers**. The rest is either Lucas' Theorem, or routine application of the CRT; what you are showing with your comments is that you are really confused about the CRT, and *only* the CRT.2012-01-01
  • 0
    So say I do 456 choose 51 mod 42, where 42's primes are 2, 3, and 7. This would imply M1=21, M2=14, M3=6, with results 0, 1, and 0. This implies the answer to mod m is 0*M1+1*M2+0*M3 = 14, but the real answer is 28. Did I miss something? EDIT: Yeah, it seems like the CRT is my main misunderstanding, here.2012-01-01
  • 1
    @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.2012-01-01
  • 0
    Also most extended euclidean algorithms, from what I can see, return the gcd given two inputs -- it doesn't find the initial inputs given the gcd of 1. Also, in your explanation, you have Mi listed twice, whereas later you use Mi and mi. This entire thing is just totally confusing me. What intermediate steps are being taken here? I appreciate the help -- I really do -- but I get lost when important steps are being excluded or skipped.2012-01-01
  • 0
    @user1123950: You are completely misinterpreting the Extended Euclidean Algorithm. The Extended Euclidean Algorithm will, given two inputs $a$ and $b$, find not only $\gcd(a,b)$, but *also* integers $x$ and $y$ such that $\gcd(a,b)=ax+by$. In the situation of the CRT, you **know** what $a$ and $b$ are: they are $m_i$ and $M_i$. You don't need to "find the initial inputs", you need to find $x$ and $y$ (which are **not** the inputs).2012-01-01
  • 2
    @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$.2012-01-01
  • 0
    @user1123950: There was a simple typo in what I wrote. But please read it carefully After finding M1, M2, and M3, you need to find expressions for 1, $1=t_1\times 2+s_1M_1$; $1=t_2\times 3+s_2M_2$; $1=t_3\times 7+s_3M_3$. So the correct computation would then be $0s_1M_1+1s_2M_2+0s_3M_3$, not $0M_1+1M_2+0M_3$ (it just happened in the previous example that $s_1=s_2=s_3=1$). Here, for the only one that matters you get $1=5(3)−1M_2$, so you actually want $1(−1)(14)=−14$, and $−14\equiv 28\pmod{42}$, giving the correct answer.2012-01-01