AoPSWiki

Want to learn how to tackle those tough AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.

Personal tools

Search

Toolbox

Lucas' Theorem

From AoPSWiki

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}$ .

Contents

1 Lemma
- 1.1 Proof
2 Proof
3 See also

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}...$

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\\&\e...$

Proof

Consider $(1+x)^n$ . If $(\overline{n_mn_{m-1}\cdots n_0})_p$ is the base $p$ representation of $n$ , then $0\leq n_k \leq p-1$ for all $0\leq k \leq m$ and $n=n_mp^m+n_{m-1}p^{m-1}+\cdots+n_1p+n_0$ . We then 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-...$

We want the coefficient of $x^i$ in $(1+x)^n$ . Since $i=i_mp^m+i_{m-1}p^{m-1}+\cdots+i_1p+i_0$ , we want the coefficient of $(x^{p^{m}})^{i_{m}}(x^{p^{m-1}})^{i_{m-1}}\cdots (x^p)^{i_1}x^{i_0}$ .

The coefficient of each $(x^{p^{k}})^{i_{k}}$ comes from the binomial expansion of $(1+x^{p^k})^{n_k}$ , which is $\binom{n_k}{i_k}$ . Therefore we take the product of all such $\binom{n_k}{i_k}$ , and thus we have

$\binom{n}{i}\equiv\prod_{k=1}^{n}\binom{n_k}{i_k}\pmod{p}$

Note that $n_k<i_k\Longrightarrow\binom{n_k}{i_k}=0\Longrightarrow\binom{n}{i}\equiv 0 \pmod{p}$ .

This is equivalent to saying that there is no $x^i$ term in the expansion of $(1+x)^n=(1+x^{p^m})^{n_m}(1+x^{p^{m-1}})^{n_{m-1}}\cdots(1+x^p)^{n_1}(1+x)^{n_0}$ .

See also

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Lucas%27_Theorem"

Categories: Theorems | Number theory

Looking for a challenging geometry text? Preparing for MATHCOUNTS or the AMC exams? Check out Art of Problem Solving's Introduction to Geometry by Richard Rusczyk.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us