So after some "fooling around" I came across this property in Pascal's triangle (which seems to repeat, and makes a lot of sense):
$\begin{pmatrix} n \\ k \end{pmatrix} \mod n = \begin{cases} n \over k, & \text{if $k | n$} \\ 0, & \text{otherwise} \end{cases} $
for: $1<k \le \lfloor n/2 \rfloor$
Its very simple, so my questions are:
- Is it true for all $n$? (I am fairly sure)
- What is the proof, if true?
I understand how the primes work (due to $\begin{pmatrix} p \\ k \end{pmatrix} \mod p = 0$ for all: $0<k<n$, but how about composites?
Kummer's Theorem states that the number of times a prime $p$ divides $\binom{n}{k}$ is equal to the number of carries when $n-k$ is added to $k$. By considering the primes dividing $n$ individually it is easy to see that $\binom{n}{k}$ is divisible by $\frac{n}{\gcd(n,k)}$. This is equivalent to your statement if $n$ and $k$ are relatively prime (about 60% of the pairs). Your statement is also true if $n$ is a product of two primes and $k$ divides $n$ (rare in general, but common for small values of $n$).