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 *p*th 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 *p*th 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.

Little typo in ‘When p = 7, the numbers are 1, 7, 28, 35, 35, 29, 7, 1.’

Thanks. Fixed that.

Might be worth calling out that the divisibility fact about the p-th row only holds for p prime, since the rest of that paragraph’s claims (adds to 2^p, etc) *do* hold for arbitrary p. (I was a bit confused, since I know row 4 was 1 4 6 4 1, until I realized the caveat.)