proof of Lucas’s theorem

Let $n\\geq m\\in\\mathbb{N}$ . Let $a_{0},b_{0}$ be the least non-negative residuesof $n,m\\pmod{p}$ , respectively. (Additionally, we set $r=n-m$ , and $r_{0}$ is theleast 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 seethat 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 thestatement and (2)– produce the same results.