I came across this : "It is possible to show that if $p$ is prime, $\binom{n}{r}$ is not divisible by $p$ if and only if the addition $r + (n-r)$, when written in base $p$, has no carries. This means that the number of entries in the $n$-th row of Pascal's triangle that are not divisible by $p$ is equal to the product over all digits $d$ of $n$ written in base $p$ of $1+d$."
Are there any good proofs of this statement?
On
It is not hard to compute that (the exponent of) highest power of $p$ dividing $n$ factorial is $\tfrac1{p-1}(n-S(n))$ where $S(n)$ is the sum of $n$'s digits in base $p$. From there it's pretty straightforward to see the connection between $\frac{n!}{(n-r)!r!}$ and the number of carries in the base-$p$ addition.
On
For two positive numbers $x$ and $y$ written in the same basis there is a carry at position $-1$ (right after the dot) when performing the addition $x+y$ if and only if $\{x\}+ \{y\}>1$. Now we have
$$x = [x]+ \{x\} \\ y = [y] + \{y\} $$ and therefore $$x+y= [x]+[y] + \{x\}+\{y\}$$ Therefore we have $$[x+y] = [x]+[y] \ \ \text{if}\ \{x\}+\{y\} <1 \\ [x+y] = [x]+[y]+1 \ \ \text{if}\ \{x\} + \{y\} \ge 1$$
In other words, the carry at position $-1$ (after the dot, when adding $x$, $y$) equals $$[x+y]-[x]-[y]$$
More generally, the carry at position $i$ for $x$, $y$ written in base $b$ is
$$\left[\frac{x+y}{b^{i+1}}\right]- \left[\frac{x}{b^{i+1}}\right]-\left[\frac{y}{b^{i+1}}\right]$$
But the exponent of $p$ in $n!$ is ( http://en.wikipedia.org/wiki/Legendre%27s_formula)
$$\sum_{l\ge 1} \left[\frac{n}{p^{l}}\right]$$
and similarly for $r$, $n-r$. Now use the formula
$$\binom{n}{r} = \frac{n!}{r! \cdot (n-r)!}$$
It seems the following.
Concerning the second statement, the addition $r + (n-r)$, when written in base $p$, has no carries iff each digit of $r$ is not greater than the respective digit of $n$. It is clear that the number of such $r$ is equal to the product over all digits $d$ of $n$ written in base $p$ of $1+d$.