# Proof of Lucas' theorem without the polynomial hint

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.

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

• You don't use the decomposition of $m$ and $n$ ? – Maman Oct 7 '15 at 19:15
• I use it since $N=n_1+n_2p+\ldots+$. – user141614 Oct 7 '15 at 22:20

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.

• Thank you, I see the global idea of your proof but my question was if it was possible to complete my proof by induction ? – Maman Oct 7 '15 at 20:06
• I cannot really see your proof. You just say that you want induction on the number of digits but have no idea how to do it. What should be completed? – user141614 Oct 10 '15 at 8:20
• +1 for the nice solution, but it does not answer the question. – guest Oct 12 '15 at 21:00