2
$\begingroup$

Let $N$ be a interger (maybe $10^{15}$) and $p$ be a prime number less than $N$. How many binomials ${n}\choose{k}$, where $n<N$, divisible by $p$? we already know that ${pm}\choose{pn}$ $\equiv$ ${m}\choose{n}$ but how to find all binomials?

$\endgroup$
2
  • 2
    $\begingroup$ Maybe, you want to look at Lucas's Theorem. $\endgroup$ Jul 24, 2015 at 10:06
  • $\begingroup$ Are you fixing $n$ or $k$? This depends on the expansion of $n$ in base $p$ $\endgroup$
    – Elaqqad
    Jul 24, 2015 at 11:35

1 Answer 1

1
$\begingroup$

I'll work it out for $N=p^l$, and you can add the unenlightening details for the general case.

There are $p(p+1)/2$ pairs of base-$p$ digits $(n_i,k_i)$ such that $n_i\ge k_i$. Thus, by Lucas' theorem there are $\left(p(p+1)/2\right)^l$ pairs $(n,k)$ such that $\binom nk$ is not divisible by $p$. Presumably you only want binomial coefficients with $k\le n$, so we also need to subtract the $p^l(p^l-1)/2$ pairs for which $k\gt n$ (none of which were counted above), so the number of binomial coefficients divisible by $p$ is

$$p^{2l}-\frac1{2^l}{p^l(p+1)^l}-\frac12p^l(p^l-1)\;.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .