Pascal’s triangle and Fermat’s little theorem

I was listening to My Favorite Theorem when Jordan Ellenberg said something in passing about proving Fermat's little theorem from Pascal's triangle. I wasn't familiar with that, and fortunately Evelyn Lamb wasn't either and so she asked him to explain.

Fermat's little theorem says that for any prime p, then for any integer a,

a^p = a (mod p).

That is, a^p and a have the same remainder when you divide by p. Jordan Ellenberg picked the special case of a = 2 as his favorite theorem for the purpose of the podcast. And it's this special case that can be proved from Pascal's triangle.

The pth row of Pascal's triangle consists of the coefficients of (x + y)^p when expanded using the binomial theorem. By setting x = y = 1, you can see that the numbers in the row must add up to 2^p. Also, all the numbers in the row are divisible by p except for the 1's on each end. So the remainder when 2^p is divided by p is 2.

It's easy to observe that the numbers in the pth row, except for the ends, are divisible by p. For example, when p = 5, the numbers are 1, 5, 10, 10, 5, 1. When p = 7, the numbers are 1, 7, 28, 35, 35, 28, 7, 1.

To prove this you have to show that the binomial coefficient C(p, k) is divisible by p when 0 < k < p. When you expand the binomial coefficient into factorials, you see that there's a factor of p on top, and nothing can cancel it out because p is prime and the numbers in the denominator are less than p.

By the way, you can form an analogous proof for the general case of Fermat's little theorem by expanding

(1 + 1 + 1 + " + 1)^p

using the multinomial generalization of the binomial theorem.