# proof of Lucas’s theorem by binomial expansion

We work with polynomials in $x$ over the integers modulo $p$.
By the binomial theorem we have $(1+x)^{p}=1+x^{p}$. More generally, by induction on $i$ we have $(1+x)^{p^{i}}=1+x^{p^{i}}$.

Hence the following holds:

 $(1+x)^{n}=(1+x)^{\left[\sum_{i=0}^{k}a_{i}p^{i}\right]}=\prod_{i=0}^{k}(1+x^{p% ^{i}})^{a_{i}}=\prod_{i=0}^{k}\sum_{b=0}^{a_{i}}{{a_{i}}\choose{b}}x^{bp^{i}}$

Then the coefficient on $x^{m}$ on the left hand side is $n\choose m$.

As $m$ is uniquely base $p$, the coefficient on $x^{m}$ on the right hand side is $\prod_{i=0}^{k}{a_{i}\choose b_{i}}$.

Equating the coefficients on $x^{m}$ on either therefore yields the result.

Title proof of Lucas’s theorem by binomial expansion ProofOfLucassTheoremByBinomialExpansion 2013-03-22 18:19:59 2013-03-22 18:19:59 whm22 (2009) whm22 (2009) 4 whm22 (2009) Proof msc 11B65