When is $\binom{n}{k}$ divisible by $n$?

Question

Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up to $n=50$). Are there any known special cases where the problem becomes easier? As a place to start I was thinking of using $e_p(n!)$ defined as:

$$e_p(n!) = \sum_{k=1}^{\infty}\left \lfloor\frac{n}{p^k}\right \rfloor$$

Which counts the exponent of $p$ in $n!$ (Legendre's theorem I believe?)

Then knowing the prime factorization of $n$ perhaps we can determine if these primes appear more times in the numerator of $\binom{n}{k}$ than the denominator.

Essentially I am looking to see if this method has any traction to it and what other types of research have been done on this problem (along with any proofs of results) before. Thanks!

Answer 1

Below is a picture of the situation. Red dots are the points of the first 256 rows of Pascal's triangle where $n\mid {n \choose k}$.

It appears that "most" values fit the bill.

One can prove the following:

Proposition: Whenever $(k, n)=1$, we have $n \mid {n\choose k}$.

This follows from the case where $n$ is a prime power (considering the various prime powers dividing $n$).

However, it happens quite often that $(k,n) \neq 1$ but $n \mid {n\choose k}$ still. For instance, $10 \mid {10\choose 4}=210$, but $(10,4) \neq 1$ (this is the smallest example). I do not think that there is a simple criterion.

In fact, it is interesting to consider separately the solutions $(n,k)$ into those which are relatively prime (which I'll call the trivial solutions) and those which are not. It appears that the non-trivial solutions are completely responsible for the Sierpinski pattern in the triangle above. Indeed, here are only the trivial solutions:

and here are the non-trivial solutions:

Let $f(n)$ be the number of $k$'s between $0$ and $n$ where $n \mid {n\choose k}$. By the proposition we have $\varphi(n)< f(n) < n$.

Question: is $$\text{lim sup } \frac{f(n)-\varphi(n)}{n}=1?$$

Here is a list plot of $\frac{f(n)-\varphi(n)}{n}$. The max value reached for $1<n<2000$ is about $0.64980544$. The blue dots at the bottom are the $n$'s such that $f(n) = \varphi(n)$.

Answer 2

Well, $n = p^2$ when $k$ is not divisible by $p.$ Also $n=2p$ for $k$ not divisible by $2,p.$ Also $n=3p$ for $k$ not divisible by $3,p.$

---

Answer 3

It is not too hard to see that if $(n,k)=p$ where $p$ is a prime then $n\mid{n\choose k}$ exactly when $$p\mid \frac{{n/p\choose k/p}}{n/p}.$$ From this we can produce a large family of nontrivial examples. For $\ell\geq 2$, $p$ a prime, $n=p(\ell!p+1)$, and $k=\ell p$ then $n\mid{n\choose k}$. The first nontrivial example of $10\mid {10\choose 4}$ corresponds to $\ell=p=2$.