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
.
Lemma
For prime and
,
![$(1+x)^{p^r}\equiv 1+x^{p^r}\pmod{p}$](http://latex.artofproblemsolving.com/7/9/3/7931ec8ec0b821c30647d45a9013d573cf554bac.png)
Proof
For all ,
. Then we have
Assume we have
. Then