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 ,
Proof
For all , . Then we have Assume we have . Then