Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

While procrastinating, I decided to play around with computing binomial symbols modulo $m$, $$\binom{n}{r} \equiv q \pmod{m}, 0 \leq q < m.$$ Using Pascal's formula, I discovered that this may be done with matrix multiplication as follows. Let $N_{r}$ be the $(r+1)$ by $(r+1)$ matrix $$N_r = [a_{ij}] = \begin{pmatrix} {1}&{1}&{0}&{0}&{0}&{\dots}\\{0}&{1}&{1}&{0}&{0}&{ }\\{0}&{0}&{1}&{1}&{0}&{ }\\{0}&{0}&{0}&{1}&{1}&{\dots}\\{0}&{0}&{0}&{0}&{1}&{ }\\{\vdots}&{ }&{ }&{\vdots}&{ }&{\ddots}\\ \end{pmatrix}.$$ Let $N_r^n = [b_{ij}]$. Then $\binom{n}{r} = b_{1(r+1)}$. Obtain $N_r^n \pmod{m}$ using repeated squaring with the binary representation of $n$, and hence $q$. The complexity seems to be $O ((r+1)^3 \log_2(n))$, not amazing compared with just computing $\frac{n (n-1) \dots (n-r+1)}{r(r-1) \dots 1}$. Of course there will be almost identical rows of $N_r^k$ which may be exploited in computing $q$ in this way so being clever might reduce the complexity to $O ((r+1)^2 \log_2(n))$.

Question: Can this algorithm for computing $q$ be improved? If this has been done, what is a reference?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

When $m$ is prime the answer is given by Lucas' theorem. The problem reduces to computing the digits of $n$ and $r$ in base $p$ which can be done in time $O(\log n)$ (there is also a constant here depending on $m$).

The general problem reduces to the case that $m$ is a prime power by the Chinese remainder theorem. The answer in this case is apparently known but I'm not familiar with it; see this paper / website by Granville.

share|improve this answer
    
Thanks Qiaochu! Most of the amusement for me is to compute $\binom{n}{r} \pmod{p_1 p_2}$, where $p_1$ and $p_2$ are distinct primes. A while ago, I thought about factorization using $\binom{n}{r} \pmod{p_1 p_2}$, arxiv.org/abs/1107.5709v1 again just playing around. –  Samuel Hambleton Sep 28 '12 at 4:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.