Pascal’s triangle has many fascinating properties. One of them is for any given prime number *p*, the number of *k*-element subsets (0< *k* < *p*) of a *p*-element set is divisible by *p*:

[tex]p | \binom{p}{k}\qquad \qquad \qquad (*)[/tex]

You can think for a while how would you prove it. There might well be an elementary combinatorial proof of [tex](*)[/tex], although I suspect that it would be rather long and tedious. Fortunately there exists a simple proof using a bit of algebra!:

If [tex]k=1[/tex] or [tex]k=p-1[/tex], then [tex]\binom{p}{k}[/tex] equals [tex]p[/tex], so the task is trivial. Suppose now that 1<k<p-1 we will use the following simple facts about a group G acting on a set X:

**Fact 1.** *X is the disjoint union of the orbits of the action.*

**Fact 2.** *The size of an orbit divides the size of the group.*

Once you know what is an action, the above facts are almost immediate. To prove [tex](*)[/tex], consider the multiplicative cyclic group of size [tex]p-1[/tex],

[tex]G=\mathbb{F}_p^*=\langle\{1,\dots,p-1\},\cdot\rangle[/tex]

where [tex]m\cdot n[/tex] is calculated mod *p*.

Let X be the set of all *k*-element subsets of [tex]\{0,\dots,p-1\}[/tex] and let G act on X by [tex]gA=\{ga\mid a\in A\}.[/tex] Let us show that the orbit of any [tex]A\in X[/tex] contains more than one element. Suppose [tex]A\in X[/tex]. Since 1< *k* < *p-1*, there are non-zero elements [tex]m\in A[/tex] and [tex]n\in \{0,\dots, p-1\}\setminus A[/tex]. Moreover since G is a group, there exists [tex]g\in G[/tex] such that [tex]g\cdot m=n[/tex] if you think of *m* and *n* as elements of *G*. But this is the same as saying [tex]n\in gA[/tex], so the orbit of A contains some set that is not A, i.e. we proved what we wanted.

By Fact 2, the orbit has exactly size *p* and so Fact 1 implies that |*X*| is divisible by *p*.

Why p divides all the numbers in one line in Pascal triangle?

I would look at the expression of (p over k) as the ratio of three factorial expressions. Obviously, p divides the numerator p!. In the denominator there is a product of k! and (p-k)! and none of the factors nor their product is divisible by p because they are produced from small numbers (< p) and p is prime.

of course.. you are right. But let me like the algebraic proof still :P

In the algebraic way you do not need to prove that (p over k)=p!/((p-k)!(k!))

In the “divisibiity proof” you do not need to know what a group action is :-)

As for me, to prove that (p over k) = p!/k!(p-k)! is not harder

than to explain what a group action is.

but of course, you may like the algebraic proof.

There’s no accounting for taste.