Skip to main content.

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 C(n,k) 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: C(n,0) , C(n,1) , ... , C(n,n)

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 less than or equal to k less than or equal to n, the following recurrence relation holds:

C(n,k) = C(n-1,k) + C(n-1,k-1),  (1)

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:

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 ( C(0,0) = 1 and C(n,k) = 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 less than or equal to m less than or equal to k less than or equal to n,

C(n,k) * C(k,m) = C(n,m) * C(n-m,k-m),  (2)

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:

Identity (2) follows.

Greatest common divisor

We show that, for 0 < m less than or equal to k < n,  gcd ( C(n,m) , C(n,k) ) > 1.

Suppose, to the contrary, that C(n,m) and C(n,k) are relatively prime.

By identity (2), C(n,m) divides C(n,k) C(k,m)

Since C(n,m) and C(n,k) are relatively prime, it follows that C(n,m) divides C(k,m)

But this is impossible, as, by combinatorial considerations, C(n,m) > C(k,m)

We conclude that C(n,m) and C(n,k) 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.


Further reading

  1. Pascal's Triangle
  2. Polynomials From Pascal's Triangle
  3. Dot Patterns and the Sierpinski Gasket
  4. Interactive Pascal's Triangle
  5. Blaise Pascal

Source: Proofs That Really Count, by Arthur T. Benjamin and Jennifer J. Quinn. See section 5.2.

Back to top