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}<b_{0}\leftrightarrow c_{0}=1\leftrightarrow b_{0}-(p-r_{0})=a_{0}<% b_{0}\leftrightarrow\binom{a_{0}}{b_{0}}=0$ . So both congruences–the one in the statement and (2)– produce the same results.

Title	proof of Lucas’s theorem
Canonical name	ProofOfLucassTheorem
Date of creation	2013-03-22 13:22:56
Last modified on	2013-03-22 13:22:56
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	7
Author	mathcam (2727)
Entry type	Proof
Classification	msc 11A07
Related topic	BinomialCoefficient