Prime Number Rows in a Pascal's Triangle

Question

Most of you know what is a Pascal's Triangle. You add the two numbers above the number you are making to make the new number below.

I've figured that for every prime number row, all numbers on the row (except for the first and last numbers, which must be 1) are divisible by the row number. The row number is also the second or second last number in the row.

The first row is row 0. (the row with a single 1)

For example, row 7 contains $1,7,21,35,35,21,7,1$.

Row 9 is not a prime number, and the numbers that the row has are $1,9,36,84,126,126,84,36,9,1$.

21 and 35 are divisible by 7.

36 and 126 are divisible by 9, but 84 isn't.

With these two examples, we can see that only numbers on prime number rows have this special characteristic.

My way of proving this theory is by doing

$n \choose r$ $\div n$

$n \choose r$ $=nCr$

For this equation $n$ will be the row number and $r$ will be the place of the number in the row;

(The first number, which is $1$ for every row is number place $0$.)

$11 \choose 2$ will give you the second number of row 11, which is 55.

55 is obviously divisible by 11, which equals to 5, and 11 is a prime.

We know that the numbers of a row equal to the row number $- 1$, so row 11 has 8 numbers. (excluding the first 2 numbers, they are 1 and the row number)

We only need to use half of the numbers (all prime numbers are odd, so two number are the same in the middle) to prove the theory since the other half of the numbers are the same.

For row 11, all we need to do is

$[$$11 \choose 2$$\div 11] +[$$11\choose 3$$\div 11]+[$$11\choose 4$$\div 11]+ [$$11\choose 5$$\div 11]$

If one of the numbers is not divisible by 11, one of the answers would not be a whole number, causing the final answer to also not be a whole number. However, if all of the numbers are multiples of 11 then the final answer would be a whole number.

The above equation would turn into:

$55 \over 11$ $+$ $ 165 \over 11$ $+$ $330 \over 11$ $+$ $462 \over 11$

$=$ $5 + 15 + 30 + 42$

$=$ $92$ which is a whole number, while all the answers are also whole numbers.

Finally, my question to you is:

(a) What is a more efficient way I can prove the theory?

(b) What makes this characteristic true? What is the math behind this?

Answer 1

What you discovered is that

For $p$ a prime number, and $n \in \{1, \dots, p-1 \}$, the binomial coefficient $$\binom{p}{n} = \frac{p!}{n!(p-n)!}$$ is divisible by $p$.

The proof is very simple. The fraction $$\frac{p!}{n!(p-n)!}$$ has a numerator divisible by $p$ ($p!= p \cdot (p-1) \cdots$) and has a denominator not divisible by $p$ (all prime factors of $n!(p-n!)$ are at most $p-1$).

Thus the fraction is divisible by $p$.

This is a very important fact in math, since it is used to prove that $$(a+b)^p \equiv a^p+b^p \pmod{p}$$ for all primes $p$.

Answer 2

Crostul's answer gives the simplest proof, but there is also a purely combinatorial way to show this. Consider the $k$-element subsets of $\{0,...,p-1\}$, and say two subsets are equivalent if one can be obtained from the other by adding $a$ to each element and reducing mod $p$, for some $a\in\{0,...,p-1\}$. This is an equivalence relation, and splits the $k$-element subsets into equivalence classes. We claim that if $0<k<p$ then each class has exactly $p$ subsets, so $\binom pk$ is $p$ times the number of classes. Clearly each class has at most $p$ subsets, and if a class has fewer than $p$ then there is some subset $S$ and two distinct $a,b\in\{0,...,p-1\}$ such that the subsets formed by adding $a$ to each element of $S$ (mod $p$) and by adding $b$ are the same. Thus $$0\in S\Longleftrightarrow a-b\pmod p\in S\Longleftrightarrow 2(a-b)\pmod p\in S\Longleftrightarrow\cdots$$ and since $p$ and $a-b$ are coprime, this means $S=\varnothing$ or $S=\{0,...,p-1\}$, contradicting our assumption on $k$.