when is $\frac{1}{n}\binom{n}{r}$ an integer

Question

So I am considering for which values of n is $a_n =\frac{1}{n}\binom{n}{r}$ an integer for all $ 1\leq r \leq n-1 $.

The first thing I did was to check the Pascal Triangle. So I guess n has to be prime.

I can show that if n is prime then $a_n$ is an integer. Is n necessarily a prime ? How can I prove the converse ?

Answer 1

If $ p |n$ and $p< n$ we have $$\frac{1}{n} \binom{n}{p} = \frac{(n-1)\dots(n-p+1)}{p!}$$

This cannot be an integer as $p| p!$ and $p \nmid (n-1)\dots(n-p+1)$.

Answer 2

Let's assume $n>1$ or the statement is trivial.

It's well known that $\dbinom{n}{r}$ is divisible by $n$ for all $r$ with $0<r<n$, when $n$ is prime. Indeed $$ \binom{n}{r}=\frac{n(n-1)\dots(n-r+1)}{r!} $$ is an integer and the denominator is not divisible by $n$, while the numerator is.

Examining a table of the binomial coefficients makes one conjecture the converse:

if $n$ divides $\dbinom{n}{r}$ for every $r$ with $0<r<n$, then $n$ is prime.

This can be proved with congruences; suppose $p$ is a prime proper factor of $n$; then $$ p^n=((p-1)+1)^n= \sum_{r=0}^n\binom{n}{r}(p-1)^r\equiv (p-1)^n+1\pmod{n} $$ If $n$ is odd, we get $p^n\equiv 0\pmod n$, that is, $n\mid p^n$.

If $n$ is even, we get $p^n\equiv 2\pmod{n}$, so $p^n=2+kn$ and, since $p\mid n$, we get $p=2$.

In both cases we conclude that $n=p^t$ for some integer $t$.

Now, a consequence of Kummer's theorem states that the maximum power of $p$ that divides $\dbinom{p^t}{p^s}$ is $p^{t-s}$. Taking $s=t-1$, we see that the maximum power of $p$ that divides $\dbinom{p^t}{p^{t-1}}$ is $p^1=p$. Since we are assuming that $p^t$ divides this binomial coefficient, we conclude $t=1$ and so $n=p^t=p$ is prime.