Exercise 4.1.35* (Lucas's Theorem)

Question

Suppose that $a = \alpha p + a_0$ and that $0 \leq a_0 < p$. Show that $a!/(\alpha! p^\alpha) \equiv (-1)^\alpha a_0! \pmod p$. Suppose also that $b = \beta p + b_0$ with $0 \leq b_0 < p$. Show that $\binom{a+b}{a} \equiv \binom{\alpha + \beta}{\beta} \binom{a_0 + b_0}{a_0} \pmod p$. Deduce that if $a = \sum_i a_ip^i$ and $b = \sum_i b_i p^i$ in base $p$, then
$$\binom{a+b}{a} \equiv \prod_i \binom{a_i + b_i}{a_i} \pmod p.$$

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\F}{\mathbb{F}}

{\bf First proof.} (Following the steps of Problem 35.)
\begin{proof} 
\begin{enumerate}
\item[(a)] Suppose that $a = \alpha p + a_0$, where $0 \leq a_0 < p$.
Then
\begin{align*}
[\![ 1, a ]\!] &= ]\!] 0, \alpha p + a_0 ]\!]\
&= ]\!] \alpha p, \alpha p + a_0 ]\!] \cup \bigcup_{1 \leq k \leq \alpha}  ]\!] (\alpha - k) p , (\alpha - k + 1)p  ]\!].
\end{align*}
Therefore
\begin{align*}
\frac{a!}{\alpha! p^\alpha} &= \frac{a!}{(\alpha p) ((\alpha - 1)p) \cdots (1\cdot p)}\
&=\prod_{i = 1}^{a_0} (\alpha p + i) \prod_{k = 1}^\alpha \prod_{i=1}^{p-1} [(\alpha -k) p + i].
\end{align*}
Moreover
$$\prod_{i = 1}^{a_0} (\alpha p + i)  \equiv \prod_{i = 1}^{a_0}i = a_0! \pmod p,$$
and, by Wilson's Theorem,
$$\prod_{i=1}^{p-1} [(\alpha -k) p + i] \equiv (p-1)! \equiv -1 \pmod p,$$
thus
$$\frac{a!}{\alpha! p^\alpha} \equiv (-1)^\alpha a_0! \pmod p.$$

\item[(b)] Now
\begin{align*}
&a = \alpha p + a_0, \qquad 0 \leq a_0 < p,\
&b = \beta p + b_0, \qquad  0 \leq b_0 < p,
\end{align*}
so that $a_0, b_0$ are respectively the last digits of $a, b$ in base $p$.
\begin{itemize}
\item Suppose first that $0 \leq a_0 + b_0< p$, so that there is no carry when we add $a_0$ and $b_0$ in base $p$. Put
$$\gamma = \alpha + \beta, \qquad c_0 = a_0 + b_0.$$
Then 
\begin{align*}
\binom{a+b}{a} &= \frac{(\gamma p + c_0)!}{(\alpha p + a_0)! (\beta p + b_0)!}\
&=\frac{\gamma!}{\alpha! \beta!}\  \frac{(\gamma p + c_0)!}{\gamma! \, p^\gamma}\  \frac{\alpha ! p^\alpha} {(\alpha p + a_0)! }\  \frac{\beta ! p^\beta} {(\beta p + b_0)! },
\end{align*}
so
\begin{align}
\binom{a+b}{a} &= \binom{\alpha + \beta}{\alpha} \ \frac{C}{A \cdot B},
\end{align}
where, by part (a), since $0 \leq c_0 = a_0 + b_0 < p$,
\begin{align*}
A &= \frac{(\alpha p + a_0)! }{\alpha ! p^\alpha} \equiv (-1)^\alpha a_0! \pmod p,\
B &= \frac {(\beta p + b_0)! }{\beta ! p^\beta}  \equiv (-1)^\beta b_0! \pmod p,\
C &= \frac{(\gamma p + c_0)!}{\gamma! \, p^\gamma}  \equiv (-1)^\gamma c_0! \pmod p.
\end{align*}
We prove
\begin{align}
\frac{C}{A \cdot B} \equiv \frac{c_0!}{a_0! b_0!} \pmod p,
\end{align}
since both members are integers, $a_0! 
ot \equiv 0 \pmod p, b_0! 
ot \equiv 0 \pmod p$, so $a_0!, b_0!$ are invertible modulo $p$, so are $A, B$, and
\begin{align*}
a_0! b_0! AB \left(\frac{C}{A \cdot B} ight)& = a_0b_0 C\
&\equiv (-1)^\gamma a_0! b_0! c_0!\
&= ((-1)^\alpha a_0!)(-1)^\beta b_0 !) c_0!\
& \equiv A B c_0!\
&= a_0! b_0! A B \left ( \frac{c_0 !}{a_0! b_0! }ight) \pmod p.
\end{align*}
After simplification by $a_0! b_0! A B$, which is invertible modulo $p$, we obtain the congruence (2). Then the congruence (1) becomes
$$\binom{a+b}{a}  \equiv  \binom{\alpha + \beta}{\alpha}  \binom{a_0 + b_0}{a_0} \pmod p.$$

\item Suppose now that $ a_0 + b_0\geq  p$, so that there is a carry when we add $a_0$ and $b_0$ in base $p$. Then there is at least a carry when we add $a,b$ in base $p$. By Problem 34 (Kummer's Theorem), $\binom{a+b}{b} \equiv 0 $ and $\binom{a_0 + b_0}{a_0} \equiv 0 \pmod p$, so
$$\binom{a+b}{b} \equiv 0 \equiv  \binom{\alpha + \beta}{\alpha}  \binom{a_0 + b_0}{a_0} \pmod p.$$
\end{itemize}
In both cases,
\begin{align}
&\binom{a+b}{a}  \equiv  \binom{\alpha + \beta}{\alpha}  \binom{a_0 + b_0}{a_0} \pmod p.
\end{align}

\item[(c)] We write $a = \sum_{i = 0}^k a_i p^i, b = \sum_{i = 0}^k b_i p^i$, with the same $k$ be introducing possibly some digits $0$ at the left of the writing of $a$ or $b$ in base $p$. Then $0 \leq a < p^{k+1}, 0 \leq b < p^{k+1}$.

We prove by induction on $k$ that, for all $a, b$ such that $0 \leq a < p^{k+1}, 0 \leq b <p^{k+1}$, where $a = \sum_{i = 0}^k a_i p^i$ and $b = \sum_{i = 0}^k b_i p^i$ are the writings of $a, b$ in base $p$,
$$\binom{a+b}{a} \equiv \prod_{i=0}^k \binom{a_i + b_i}{a_i} \pmod p.$$

\begin{itemize}
\item If $k = 1$ then $a = a_0, b = b_0$, so $\binom{a+b}{a} = \binom{a_0 + b_0}{a_0} = \prod_{i=0}^0 \binom{a_i + b_i}{a_i}.$

\item Suppose that the property is true for all integers less that $p^{k}$, and take $a,b$ such that $0 \leq a < p^{k+1}, 0 \leq b < p^{k+1}$. We write $a, b$ in base $p$ in the form $a = \sum_{i=0}^k a_i p^i, b = \sum_{i = 0}^k b_i p^i$. Then $a = \alpha p + a_0, b = \beta p+ b_0$, where
$$\alpha = \sum_{i = 1}^k a_i p^{i-1} = \sum_{j=0} ^{k-1} a'_j p^j< p^k,\qquad \beta= \sum_{i = 1}^k b_i p^{i-1} = \sum_{j=0}^{p-1} b'_j p^j < p^k,$$
where $a'_j= a_{j+1}, b'_j = b_{j+1}$ for $ j= 1, 2,\ldots, k-1$ are the digits of $\alpha, \beta$ in base $p$.

The induction hypothesis applied to $\alpha, \beta$ gives
\begin{align*}
\binom{\alpha + \beta}{\alpha} &\equiv \prod_{j = 0}^{k-1} \binom{a'_j + b'_j}{a'_j}\
&= \prod_{i = 1}^k \binom{a'_{i-1}+ b'_{i-1}}{a'_{i-1}}&(i = j+1)\
&=\prod_{i = 1}^k \binom{a_i+ b_i}{a_i} \pmod p.\
\end{align*}
Then, by part (b),
\begin{align*}
\binom{a+b}{b}  & \equiv  \binom{\alpha + \beta}{\alpha}  \binom{a_0 + b_0}{a_0}\
&\equiv \left ( \prod_{i = 1}^k \binom{a_i+ b_i}{a_i} ight) \binom{a_0 + b_0}{a_0} \
& =  \prod_{i = 0}^k \binom{a_i+ b_i}{a_i}.
\end{align*}
\item The induction is done, thus the property is true for all $a,b$.
\end{itemize}
In conclusion, if $a = \sum_{i = 0}^k a_i p^i, b = \sum_{i = 0}^k b_i p^i$, where $0 \leq a_i < p, 0 \leq b_i < p$ for all $i$,
$$\binom{a+b}{a} \equiv \prod_{i = 0}^k  \binom{a_i + b_i}{a_i} \pmod p.$$
\end{enumerate}

\bigskip
{\bf Second proof} (From a paper of N.J.Fine, 1947)
\begin{proof}
We show first the Lucas's Theorem:

\bigskip
{\bf Theorem.}{\it If $n = \sum_{i=0}^k n_i p^i$ and  $a = \sum_{i = 0}^k a_i p^i$ are the writings of $n$ and $a$ in base $p$, then 
$$\binom{n}{a} = \prod_{i=0}^k \binom{n_i}{a_i}.$$
}

We expand $f(x) = (1+x)^{n}$ in $\F_p[x]$, where $\F_p$ is the field with $p$ elements.

First 
$$(1+ x)^{n} = \sum_{k= 0}^{n} \binom{n}{i} x^i,$$
and the coefficient of $x^a$ is $\binom{n}{a}$.

Next, since  the characteristic  of $\F_p$ is $p$, $(1 + x)^{p^i} = 1 + x^{p^i}$ for all $i \in \N$, therefore
\begin{align*}
(1+ x)^{n} &= (1+x)^{\sum_{i=0}^k n_i p^i}\
&= \prod_{i = 0}^k (1+x)^{n_i p^i}\
&= \prod_{i = 0}^k  [(1+x)^{p^i}]^{n_i}\
&= \prod_{i = 0}^k  (1+x^{p^i})^{n_i}\
&=  \prod_{i = 0}^k \sum_{j=0}^{n_i} \binom{n_i}{j} x^{jp^i}\
&= \sum_{(j_0,j_1,\ldots,j_k) \in [\![ 0,n_0 ]\!] 	imes \cdots 	imes[\![ 0,n_k ]\!]} \binom{n_0}{j_0} \binom{n_1}{j_1} \cdots \binom{n_k}{j_k}  x^{j_0+j_1p + \cdots j_k p^k}.
\end{align*}

\begin{itemize}
\item If $a_i \leq n_i$ for all indices $i \in [\![0, k]\!]$, then there is at least a $k+1$-tuple $(j_0,j_1,\ldots,j_k) \in [\![ 0,n_0 ]\!] 	imes \cdots [\![ 0,n_k ]\!]$ such that $a = j_0+j_1p + \cdots j_k p^k$, which is 
$$(j_0,j_1,\ldots,j_k) = (a_0,a_1, \ldots, a_k).$$
The unicity of the writing of $a$ in base $p$ shows that there is exactly one such $(j_0,j_1,\ldots,j_k)$.

This prove that the coefficient of $x^a$ in $f(x)$ is 
$$\binom{n}{a} \equiv \binom{n_0}{a_0} \binom{n_1}{a_1} \cdots \binom{n_k}{a_k} \pmod p.$$

\item If there is some index $i$ for which $a_i >n_i$, then there is no  $(j_0,j_1,\ldots,j_k) \in [\![ 0,n_0 ]\!] 	imes \cdots 	imes  [\![ 0,n_k ]\!]$ such that $a = j_0+j_1p + \cdots j_k p^k$, so the coefficient $\binom{n}{a}$ of $x^a$ is zero modulo $p$. Moreover $\binom{n_i}{a_i} = 0$, so
$$\binom{n}{a} \equiv 0 \equiv  \binom{n_0}{a_0} \binom{n_1}{a_1} \cdots \binom{n_k}{a_k} \pmod p.$$
\end{itemize}

In both cases, 
$$\binom{n}{a} \equiv \binom{n_0}{a_0} \binom{n_1}{a_1} \cdots \binom{n_k}{a_k} \pmod p.$$
\end{proof}
Now we can prove the result of Problem 35. Here $a = \sum_{i=0}^k a_i p^i$ and $b = \sum_{i=0}^k b_i p^i$ are given.

If there is some index $i$ such that $a_i + b_i \geq p$, then there is at least a carry in the addition of $a$ and $b$ in base $p$. By Kummer's Theorem (Problem 34), $\binom{a+b}{a} \equiv 0 \pmod p$. Moreover, for the same reason $\binom{a_i+b_i}{a_i} \equiv 0 \pmod p$. So
$$\binom{a+b}{a} \equiv 0 \equiv \prod_{i = 0}^k  \binom{a_i + b_i}{a_i} \pmod p.$$

Otherwise $0 \leq a_i + b_i < p$ for all $i$, so $n_i =a_i +b_i$ is the $i$-th digit of $n = a+b$ in base $p$. Therefore, the Lucas's Theorem gives
$$\binom{a+b}{a} = \binom{n}{a} \equiv \sum_{i=0}^k n_i p^i  = \binom{a_i + b_i}{a_i} \pmod p.$$

\end{proof}
Note 1: Conversely, if we know the result of Problem 35 by the first proof, we can prove the Lucas's Theorem. We write $\binom{n}{a} = \binom{a+b}{a}$, where $b = n- a$.

If there is no carry when we add $a,b$ in base $p$, then $n_i = a_i + b_i$ for all $i$, so
$$\binom{n}{a} = \binom{a+b}{a} \equiv  \prod_{i = 0}^k  \binom{a_i + b_i}{a_i} =  \prod_{i = 0}^k  \binom{n_i}{a_i}.$$

Otherwise, if there is a carry, then
$$\binom{n}{a} = \binom{a+b}{a} \equiv 0\pmod p.$$
Moreover, if there is a carry at the index $i$, $a_i + b _i = p + n_i,$ thus $n_i = a_i  - (p - b_i) < a_i$, so $\binom{n_i}{a_i} = 0$, and then
$$\binom{n}{a} \equiv 0 \equiv \prod_{i=0}^k \binom{n_i}{a_i} \pmod p.$$ 
This proves Lucas's Theorem with the result of Problem 35.

The equivalence between Problem 35 and Lucas's Theorem is not obvious without the Kummer's Theorem (Problem 34).

\bigskip
Note 2:
We can compare with Sage the results of Problem 35 and Lucas Theorem to compute $\binom{n}{a}$ modulo $p$. For instance, for $n =17, a = 12, p = 7$, we obtain in base $7$
$$12 + 5 = 15_7 + 05_7 = 23_7 = 17,$$
so $a_0 = 5, a_1 = 1, b_0 = 5, b_1 = 0, n_0 = 3, n_1 = 7$.

With Lucas's Theorem, 
$$\binom{17}{12}  = \binom{23_7}{15_7} \equiv  \binom{2}{1} \binom{3}{5} \equiv 0 \pmod 7,$$
and with the result of Problem 35,
$$\binom{17}{12} = \binom{12+5}{12} \equiv  \binom{15_7 + 05_7}{15_7} = \binom{1}{1} \binom{10}{5} = 252 = 36 \cdot 7 \equiv  0 \pmod 7.$$
\begin{verbatim}
def decomposition(n, p):
    l = []
    while n != 0:
        q, r = n // p, n % p
        n = q
        l.append(r)
    return l
    
def lucas(n, a, p):
    la = decomposition(a, p)
    ln = decomposition(n, p)
    k = max(len(la), len(ln))
    for i in range(len(la), k):
        la.append(0)
    for i in range(len(ln), k):
        ln.append(0)
    res = 1
    for i in range(k):
        res *= binomial(ln[i], la[i])
    return res % p
    
def niven(a, b, p):
    la = decomposition(a, p)
    lb = decomposition(b, p)
    k = max(len(la), len(lb))
    for i in range(len(la), k):
        la.append(0)
    for i in range(len(lb), k):
        lb.append(0)
    res = 1
    for i in range(k):
        res *= binomial(la[i]+ lb[i], la[i])
    return res % p
    
n = 17
p = 7
b1, b2, b3 = [], [], []
for a in range(n + 1):
    b1.append(binomial(n, a) % p)
    b2.append(lucas(n, a, p))
    b3.append(niven(a, n - a ,p))
print(b1)
print(b2)
print(b3)  
      	
[1, 3, 3, 1, 0, 0, 0, 2, 6, 6, 2, 0, 0, 0, 1, 3, 3, 1]
[1, 3, 3, 1, 0, 0, 0, 2, 6, 6, 2, 0, 0, 0, 1, 3, 3, 1]
[1, 3, 3, 1, 0, 0, 0, 2, 6, 6, 2, 0, 0, 0, 1, 3, 3, 1]

\end{verbatim}

Exercise 4.1.35* (Lucas's Theorem)

Answers

Comments

Exercise 4.1.35* (Lucas's Theorem)

Answers

Comments

Add answer