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.

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?

share|improve this question
I believe the converse is not true. ${4\choose1} = 4 \equiv 0 \mod4$. –  Lee Yiyuan 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$ –  Soke 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. –  Soke 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 2

up vote 1 down vote accepted

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.

share|improve this answer

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}$.

share|improve this answer

Your Answer


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.