Lucas' Theorem

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

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)

Proof

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

$\begin{eqnarray*}(1+x)^n&=&(1+x)^{n_mp^m+n_{m-1}p^{m-1}+\cdots+n_1p+n_0}\\

&=&[(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. Unknown error_msg)

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 .

See also

• Combinatorics
• Generating function
• Binomial Theorem