# 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 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 .