# 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}}\left(\genfrac{}{}{0pt}{}{{a}_{i}}{b}\right){x}^{b{p}^{i}}$$ |

Then the coefficient on ${x}^{m}$ on the left hand side is $\left(\genfrac{}{}{0pt}{}{n}{m}\right)$.

As $m$ is uniquely base $p$, the coefficient on ${x}^{m}$ on the right hand side is ${\prod}_{i=0}^{k}\left(\genfrac{}{}{0pt}{}{{a}_{i}}{{b}_{i}}\right)$.

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

Title | proof of Lucas’s theorem by binomial expansion |
---|---|

Canonical name | ProofOfLucassTheoremByBinomialExpansion |

Date of creation | 2013-03-22 18:19:59 |

Last modified on | 2013-03-22 18:19:59 |

Owner | whm22 (2009) |

Last modified by | whm22 (2009) |

Numerical id | 4 |

Author | whm22 (2009) |

Entry type | Proof |

Classification | msc 11B65 |