26
$\begingroup$

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.

Picture of a Pascal's Triangle

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?

$\endgroup$
3
  • 7
    $\begingroup$ en.wikipedia.org/wiki/Kummer%27s_theorem $\endgroup$ Jun 28, 2018 at 7:44
  • 5
    $\begingroup$ Adding the numbers in a row is not helpful. If all of a set of numbers are divisible by $p$, this does imply that their sum is divisible by $p$, but the reverse is not true: if a sum of numbers is divisible by $p$, you can't conclude that all of the summed numbers are divisible by $p$. $\endgroup$
    – aschepler
    Jun 28, 2018 at 10:38
  • 2
    $\begingroup$ The converse is true in the sense that if n is a number which divides every element of the corresponding row in Pascal's triangle (excluding the outer 1's) then n is prime. This yields an utterly impracticable test for primality. $\endgroup$ Jun 28, 2018 at 17:32

2 Answers 2

55
$\begingroup$

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

$\endgroup$
3
15
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ It's worth noting that this argument generalizes to show: suppose $p$ is prime, $X$ is finite and $f : X \to X$ is such that $f^p = f \circ f \circ \cdots \circ f$ is equal to the identity function. Then $|X| \equiv |\{ x\in X \mid f(x) = x \}| \pmod{p}$. In this case, $f$ was the function which takes a subset and adds 1 to every number, wrapping around $p$ to $0$. For other applications: if you apply it to the set of $p$-tuples on $\{ 0, \ldots, a-1 \}$ with $f$ being the operation of cycling elements of the tuple one to the right, you get Fermat's Little Theorem, $a^p \equiv a \pmod{p}$. $\endgroup$ Jun 28, 2018 at 20:42
  • 2
    $\begingroup$ Similarly, if you apply it to the set of $pb$-element subsets of $\{ 0, \ldots, pa-1 \}$ with $f$ being adding $a$ to each element and modding out by $pa$, you get $\binom{pa}{pb} \equiv \binom{a}{b} \pmod{p}$. In abstract algebra, you would study this as an "action of $\mathbb{Z} / p \mathbb{Z}$ on a set" and analyze the "orbits of this action" but at its heart it would be the same argument. $\endgroup$ Jun 28, 2018 at 20:44
  • 1
    $\begingroup$ This same proof idea applies to other combinatorial triangles. Both ${p \brack k}$ (Stirling numbers 1st kind) and ${p \brace k}$ (Stirling numbers 2nd kind) are multiples of $p$ when $p$ is prime and $0<k<p$. $\endgroup$ Apr 15, 2022 at 15:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .