Proof of Lucas' theorem without the polynomial hint

Question

I try to prove that for $p$ a prime number , $m$, $n$ two positive integers we have : $\binom mn \equiv \prod \limits_{i=0}^{k} \binom {m_i}{n_i} \ [p]$ with : $m=m_0+m_1 p+...+m_k p^k$ and $n=n_0+n_1 p+...+n_k p^k$.

My idea was to solve it by induction on $k$ :

-If $k=0$ then I have $m=m_0$ and $n=n_0$, so $\binom mn \equiv \binom{m_0}{n_0} \ [p]$

-Now suppose that we have $\binom mn \equiv \prod \limits_{i=0}^{k} \binom {m_i}{n_i} \ [p]$

Try to show that : $\binom mn \equiv \prod \limits_{i=0}^{k+1} \binom {m_i}{n_i} \ [p]$ with $m=m_0+m_1 p+...+m_k p^k+m_{k+1}p^{k+1}$ and $n=n_0+n_1 p+...+n_k p^k+n_{k+1} p^{k+1}$.

I don't know if it's the right way to proceed.

Thanks in advance !

Answer 1

A combinatorial proof:

Let $n=Np+n_0$ and $k=Kp+k_0$ where $N=\left[\tfrac{n}{p}\right]$, $K=\left[\tfrac{k}{p}\right]$, $0\le n_0,k_0<p$ are the remainders modulo $p$.

Group the numbers $1,2,\ldots,n$ into "blocks": $$ \big[1,2,\ldots,p\big) \quad \big[p+1,\ldots,2p\big] \quad \ldots \quad \big[(N-1)p+1,\ldots,Np\big] \quad \big[Np+1,\ldots,Np+n_0\big] \tag{1} $$ The first $N$ blocks, each having $p$ elements, will be called "complete blocks"; the last block that has only $n_0$ elements is the "short block".

Represent the $k$-element subsets of $\{1,\ldots,n\}$ by lottery tickets: create $\binom{n}{k}$ copies of (1), and cross $k$ numbers in every copy.

Now we say that two lottery tickets are equivalent if:

• The two tickets differ only in one complete block, say in the $j$th one;

• Each of the first $j-1$ blocks is either empty (containing no cross) or full (all $p$ numbers are crossed);

• The $j$th blocks of the two tickets can be obtained from each other by rotating the crosses within the group, i.e. increasing each number by the same vaule modulo $p$.

This relation arranges many of the the lottery tickets in groups with $p$ tickets in each group, but some tickets remain not grouped. Those tickets are not grouped in which every complete group is either empty or full. In such tickets there must be $K$ fully crossed of the $N$ complete groups, and there must be $k_0$ crosses in the short group. So, the number of ungrouped tickets is $\binom{N}{K}\cdot\binom{n_0}{k_0}$. (This is valid for $k_0>n_0$ as well.) Hence, $$ \binom{n}{k} \equiv \binom{N}{K}\cdot\binom{n_0}{k_0} \pmod{p}. \tag2 $$ From 2 the statement follows by induction.

Answer 2

Another approach is considering the factors in $$ \binom{n}{k} = \frac{n!}{k!\cdot(n-k)!} $$ modulo $p$ and applying Wilson.

If $k_0\le n_0$ then $$ \binom{n}{k} = \frac{ \big(1\cdot2\cdots(p-1)\big)\cdot p \cdot \big((p+1)\cdot(p+2)\cdots(2p-1)\big)\cdot 2p \cdots Np \cdots \big((Np+1)\cdots n\big) }{ \Big[\big(1\cdot2\cdots(p-1)\big)\cdot p \cdots Kp \cdot \big((Kp+1)\cdots k\big) \Big] \cdot \Big[\big(1\cdot2\cdots(p-1)\big)\cdot p \cdots (N-K)p \cdots \big(((N-K)p+1)\cdots (n-k)\big)\Big]} \equiv \\ \equiv \frac{p\cdot 2p\cdots Np \cdot \big((Np+1)\cdots n\big)}{ \Big[p\cdot 2p\cdots Kp \cdot \big((Kp+1)\cdots k\big)\Big]\cdot \Big[p\cdot 2p\cdots (N-K)p \cdot \big(((N-K)p+1)\cdots (n-k)\big)\Big]} \equiv \\ \equiv \binom{N}{K} \cdot \binom{n_0}{k_0} \pmod{p}. $$ If $k_0>n_0$ then there are by one fewer multiples of $p$ among the factors in the denominator. The multiples of $p$ give $$ \frac{p\cdot2p\cdots Np}{(p\cdots Kp)\cdot(p\cdots(N-K-1)p)} = Np\cdot \binom{N-1}{K}, $$ that is divisible by $p$.