How many binomials are divisible by $p$?

Question

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?

Answer 1

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)\;.$$