Lucas' Theorem

Let be a prime. If is the base representation of and is the base representation of , where , Lucas' Theorem states that

Proof

Lemma

For prime and ,

Proof

For all , . Then we have that

$\begin{eqnarray*}(1+x)^p&\equiv &\binom{p}{0}+\binom{p}{1}x+\binom{p}{2}x^2+\cdots+\binom{p}{p-1}x^{p-1}+\binom{p}{p}x^p\\ &\equiv& 1+x^p\pmod{p}\end{eqnarray*}$ (Error compiling LaTeX. Unknown error_msg)

Assume we have . Then

$\begin{eqnarray*}(1+x)^{p^{k+1}}

&\equiv&\left((1+x)^{p^k}\right)^p\\ &\equiv&\left(1+x^{p^k}\right)^p\\ &\equiv&\binom{p}{0}+\binom{p}{1}x^{p^k}+\binom{p}{2}x^{2p^k}+\cdots+\binom{p}{p-1}x^{(p-1)p^k}+\binom{p}{p}x^{p^{k+1}}\\

&\equiv&1+x^{p^{k+1}}\pmod{p}\end{eqnarray*}$ (Error compiling LaTeX. Unknown error_msg)

See also

• Combinatorics
• Generating function