Lesson 6

Repeatedly applying the same idea gives \[(1+x)^{p^i}\equiv 1+x^{p^i}\pmod p\] for every \(i\ge 0\). Now we can prove the theorem that fully controls Pascal's triangle modulo \(p\).

Theorem (Lucas). Let \(p\) be prime. Write \(n\) and \(k\) in base \(p\): \[n=n_{0}+n_{1}p+\dotsb+n_{r}p^{r},\qquad k=k_{0}+k_{1}p+\dotsb+k_{r}p^{r},\] where \(0\le n_{i},k_{i}<p\). Then \[\binom{n}{k}\equiv \prod_{i=0}^{r}\binom{n_i}{k_i}\pmod p.\] We use the convention that \(\binom{n_i}{k_i}=0\) when \(k_{i}>n_{i}\).

Proof. We work with polynomials whose coefficients are taken modulo \(p\). Since \(n=n_{0}+n_{1}p+\dotsb+n_{r}p^{r}\), we have \[(1+x)^{n}=\prod_{i=0}^{r}(1+x)^{n_ip^i}=\prod_{i=0}^{r}\left((1+x)^{p^i}\right)^{n_i}.\] Using \((1+x)^{p^i}\equiv 1+x^{p^i}\pmod p\), we get \[(1+x)^{n}\equiv \prod_{i=0}^{r}\left(1+x^{p^i}\right)^{n_i}\pmod p.\] After expanding each factor on the right, \[\prod_{i=0}^{r}\left(1+x^{p^i}\right)^{n_i}=\prod_{i=0}^{r}\sum_{j=0}^{n_i}\binom{n_i}{j}x^{jp^i}.\] To get the term \(x^{k}=x^{k_0+k_1p+\dotsb+k_rp^r}\), we must choose the term \(x^{k_ip^i}\) from the \(i\)-th factor for every \(i\). This choice is unique because base-\(p\) notation is unique. Thus the coefficient of \(x^{k}\) on the right is \[\prod_{i=0}^{r}\binom{n_i}{k_i}.\] On the left, the coefficient of \(x^{k}\) is \(\binom{n}{k}\). Comparing coefficients modulo \(p\) proves the theorem.◼