Solution to puzzle 93: Pascal's triangle

Show that any two elements (both greater than one) drawn from the same row of Pascal's triangle have greatest common divisor (gcd) greater than one. For example, the greatest common divisor of 28 and 70 is 14.

Pascal's triangle comprises binomial coefficients

Each element in Pascal's triangle is obtained by adding the two elements diagonally above. (With suitable boundary conditions; see below.)
The binomial coefficient may be defined as the number of ways of choosing k outcomes out of n possibilities, ignoring order.
We prove the well known result that row n of Pascal's triangle comprises the sequence of binomial coefficients: , , ... ,

row 0:                     1
row 1:                   1   1
row 2:                 1   2   1
row 3:               1   3   3   1
row 4:             1   4   6   4   1
row 5:           1   5  10  10   5   1
row 6:         1   6  15  20  15   6   1
row 7:       1   7  21  35  35  21   7   1
row 8:     1   8  28  56  70  56  28   8   1

To establish this result we first note that, for 1 k n, the following recurrence relation holds:

This follows from a simple direct counting, or combinatorial, argument.

How many ways can we choose a committee of k students from a class of n students? We count in two different ways:

By definition, there are ways.
Condition on whether or not student number 1 is on the committee. There are committees that exclude student 1, and committees that include student 1.

Recurrence relation (1) follows. This relation is equivalent to the method of constructing Pascal's triangle by adding two adjacent numbers and writing the sum directly underneath.
With suitable initial conditions ( = 1 and = 0 for n < k), it is now easy to prove by mathematical induction that Pascal's triangle comprises binomial coefficients.

A binomial coefficient identity

We show that, for 0 m k n,

Again we make use of a combinatorial argument. In a class of n students, how many ways can we choose a committee of k students that contains a subcommittee of m students? Counting in two different ways:

We can choose the committee in ways, then choose the subcommittee in ways.
We can first choose the subcommittee in ways. Then, from the remaining n − m students, choose the k − m students to be on the committee but not the subcommittee in ways.

Identity (2) follows.

Greatest common divisor

We show that, for 0 < m k < n, gcd ( , ) > 1.

Suppose, to the contrary, that and are relatively prime.

By identity (2), divides

Since and are relatively prime, it follows that divides

But this is impossible, as, by combinatorial considerations, >

We conclude that and are not relatively prime; that is, any two elements (both greater than one) drawn from the same row of Pascal's triangle have greatest common divisor greater than one.

Remarks

This result was first proved by Erdös and Szekeres in 1978.

Solution to puzzle 93: Pascal's triangle

Pascal's triangle comprises binomial coefficients

A binomial coefficient identity

Greatest common divisor

Remarks

Further reading