# proof of Lucas’s theorem

Let $n\geq m\in\mathbb{N}$. Let $a_{0},b_{0}$ be the least non-negative residues of $n,m\pmod{p}$, respectively. (Additionally, we set $r=n-m$, and $r_{0}$ is the least non-negative residue of $r$ modulo $p$.) Then the statement follows from

 $\binom{n}{m}\equiv\binom{a_{0}}{b_{0}}\binom{\left\lfloor\frac{n}{p}\right% \rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}\pmod{p}.$

We define the ’carry indicators’ $c_{i}$ for all $i\geq 0$ as

 $c_{i}=\left(\begin{array}[]{lll}1&\mbox{if}&b_{i}+r_{i}\geq p\\ 0&\mbox{otherwise}\end{array}\right.,$

and additionally $c_{-1}=0$.

The special case $s=1$ of Anton’s congruence  is:

 $\left(n!\right)_{p}\equiv\left(-1\right)^{\left\lfloor\frac{n}{p}\right\rfloor% }\cdot a_{0}!\pmod{p},$ (1)

where $a_{0}$ as defined above, and $\left(n!\right)_{p}$ is the product of numbers $\leq n$ not divisible by $p$. So we have

 $\frac{n!}{\left\lfloor\frac{n}{p}\right\rfloor!p^{\left\lfloor\frac{n}{p}% \right\rfloor}}=\left(n!\right)_{p}\equiv(-1)^{\left\lfloor\frac{n}{p}\right% \rfloor}\cdot a_{0}!\pmod{p}$

When dividing by the left-hand terms of the congruences for $m$ and $r$, we see that the power of $p$ is

 $\left\lfloor\frac{n}{p}\right\rfloor-\left\lfloor\frac{m}{p}\right\rfloor-% \left\lfloor\frac{r}{p}\right\rfloor=c_{0}$

So we get the congruence

 $\frac{\binom{n}{m}}{\binom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor% \frac{m}{p}\right\rfloor}\cdot p^{c_{0}}}\equiv(-1)^{c_{0}}\cdot\binom{a_{0}}{% b_{0}},$

or equivalently

 $\left(\frac{-1}{p}\right)^{c_{0}}\cdot\binom{n}{m}\equiv\binom{a_{0}}{b_{0}}% \binom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right% \rfloor}\pmod{p}.$ (2)

Now we consider $c_{0}=1$. Since

 $a_{0}=b_{0}+r_{0}-\underbrace{pc_{0}=p},$

$b_{0}+r_{0}. So both congruences–the one in the statement and (2)– produce the same results.

Title proof of Lucas’s theorem ProofOfLucassTheorem 2013-03-22 13:22:56 2013-03-22 13:22:56 mathcam (2727) mathcam (2727) 7 mathcam (2727) Proof msc 11A07 BinomialCoefficient