Lucas' Theorem

Lucas' Theorem states that for any prime $p$ and any positive integers $n\geq i$ , if $(\overline{n_mn_{m-1}\cdots n_0})_p$ is the representation of $n$ in base $p$ and $(\overline{i_mi_{m-1}\cdots i_0})_p$ is the representation of $i$ in base $p$ (possibly with some leading $0$ s) then $\binom{n}{i}\equiv \prod_{j=0}^{m}\binom{n_j}{i_j}\pmod{p}$ .

Lemma

For $p$ prime and $x,r\in\mathbb{Z}$ ,

$(1+x)^{p^r}\equiv 1+x^{p^r}\pmod{p}$

Proof

For all $1\leq k \leq p-1$ , $\binom{p}{k}\equiv 0 \pmod{p}$ . Then we have $\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*}$ Assume we have $(1+x)^{p^k}\equiv 1+x^{p^k}\pmod{p}$ . 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*}$

Page

Toolbox

Search

Lucas' Theorem

Lemma

Proof

See also