# Lucas' Theorem

**Lucas' Theorem** states that for any prime and any positive integers , if is the representation of in base and is the representation of in base (possibly with some leading s) then .

## Contents

## Lemma

For prime and ,

### Proof

For all , . Then we have Assume we have . Then

## Proof

Consider . If is the base representation of , then for all and . We then have

&=&[(1+x)^{p^m}]^{n_m}[(1+x)^{p^{m-1}}]^{n_{m-1}}\cdots[(1+x)^p]^{n_1}(1+x)^{n_0}\\ &\equiv&(1+x^{p^m})^{n_m}(1+x^{p^{m-1}})^{n_{m-1}}\cdots(1+x^p)^{n_1}(1+x)^{n_0}\pmod{p}

\end{eqnarray*}$ (Error compiling LaTeX. ! Missing \endgroup inserted.)We want the coefficient of in . Since , we want the coefficient of .

The coefficient of each comes from the binomial expansion of , which is . Therefore we take the product of all such , and thus we have

Note that .

This is equivalent to saying that there is no term in the expansion of .