# Combinations mod $n$ property

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:

1. Is it true for all $n$? (I am fairly sure)
2. 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?

• $\binom{4}{2}=6\equiv 2\mod 4$. However, it is in general true that different combinations from the same row (except the ends) have a gcd greater than 1. – Robert Wolfe Jul 16 '14 at 20:29
• $\binom{14}{4} = 1001 \equiv 7 \pmod{14}$ – Daniel Fischer Jul 16 '14 at 20:38
• $\dbinom{12}{6} = 924 \equiv 0\pmod{12}$ – rogerl Jul 16 '14 at 20:39
• Thanks for the counterexamples, I still find it interesting how a large amount of numbers follow this pattern. – Dane Bouchie Jul 16 '14 at 21:04
• Given $n$, I wonder how many $k$ follow this pattern... That might yield something interesting. – apnorton Jul 16 '14 at 21:23

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