# Help proving ${n \choose k} \equiv 0 \pmod n$ for all $k$ such that $0<k<n$ iff $n$ is prime.

I can prove the $n$ is prime case: If $n$ is prime, then since $k < n$ and $n$ is prime, the factor of $n$ in the numerator won't be cancelled out.

So the question boils down to

Let an integer $n>1$ be such that $n$ divides $\binom nk$ whenever $0<k<n$; show that $n$ is prime.

If $n$ is composite and even, then ${n \choose 2} = \frac{n(n+1)}{2}$ is not divisible by $n$ because it 'lost' a $2$ factor (and $n+1$ is odd), which takes care of this case.

However, I'm somewhat at a loss for what to do when $n$ is composite and odd. Any hints?

• I believe the converse is not true. ${4\choose1} = 4 \equiv 0 \mod4$. – Yiyuan Lee Feb 3 '14 at 13:51
• Sorry if it was unclear, I meant for all $k$ such that $0 < k< n$, so then ${4 \choose 2} \equiv 2 \pmod 4$ – MCT Feb 3 '14 at 13:53
• Furthermore I don't believe this is a duplicate -- I need help with proving the converse of what is asked in the linked question; as far as I know these are two separate questions. – MCT Feb 3 '14 at 14:00
• ${9\choose 4}\equiv 0 \mod 9$ – clark Feb 3 '14 at 14:09
• @clark, Lee: You should repeat quantors. – Martin Brandenburg Feb 3 '14 at 14:09

## 2 Answers

It is well known (Kummer's theorem) that the multiplicity of a prime number $p$ in a binomial coefficient $\binom{a+b}a$, with $a,b\in\mathbf N$, equals the number of times a carry is produced when representing $a,b$ as numbers in base$~p$ and performing the addition $a+b$. Now if $n$ is composite and $p$ a prime divisor of$~n$, then first consider the case that $n$ is not a power of $p$. This means that in base$~p$ it has either two nonzero digits or a single nonzero digit other than $1$. Now by separating the nonzero digits in two non-empty groups respectively representing $a,b$, or doing similarly after writing the single nonzero digit as a carry-less sum of other digits, one can achieve $n=a+b$ without any carry in base$~p$; this means that $p\nmid\binom na$ and a fortiori $n$ does not divide $\binom na$. We are left with the case that $n=p^i$ for some $i\geq2$. But now with $a=p^i-p^{i-1}$ and $b=p^{i-1}$, their base$~p$ representations are $a=[p-1,0,\ldots,0]_p$ respectively $b=[1,0,\ldots,0]_p$ (with $i-1$ digits in each number), so perfoming $a+b$ produces a carry only once, and there is only one factor$~p$ in $\binom na$, which is therefore not divisible by $n=p^i$. This proves what you want.

Here's a simple proof by contrapositive. Suppose $n$ is not prime. Let $p$ be a prime divisor of $n$ and write $n=p^d q$, where $p\not\mid q$. Clearly $0<p<n$. Then $$\binom{n}{p}=\frac{p^d q\cdot(p^dq-1)\cdots (p^dq-(p-1))}{p!}\textrm.$$ There are exactly $d$ factors of $p$ in the numerator, all from the the term $p^dq$, because each term after that one differs from a multiple of $p$ by less than $p$ (and therefore can't be a multiple of $p$). One of those $d$ factors is cancelled out by the $p$ in the denominator, so $p^d \not\mid \binom{n}{p}$, which guarantees that $n\not\mid \binom{n}{p}$.