Théorème de Lucas

En théorie des nombres, le théorème de Lucas exprime le reste de la division du coefficient binomial ${\tbinom {n}{k}}$ par un nombre premier $p$ en termes du développement en base $p$ des entiers $n$ et $k$.

Le théorème de Lucas a été publié en 1878 par Édouard Lucas.

Énoncé

Pour des entiers $n$ et $k$ positifs ou nuls et un nombre premier $p$, on a la relation de congruence suivante :

${\binom {n}{k}}\equiv \prod _{i=0}^{r}{\binom {n_{i}}{k_{i}}}{\pmod {p}},$

où

$n=n_{r}p^{r}+n_{r-1}p^{r-1}+\cdots +n_{1}p+n_{0},$

et

$k=k_{r}p^{r}+k_{r-1}p^{r-1}+\cdots +k_{1}p+k_{0}$

sont les développements respectifs de $n$ et $k$ en base $p$.

Corollaire

Un coefficient binomial ${\tbinom {n}{k}}$ est divisible par un nombre premier $p$ si et seulement si au moins un chiffre $k_{i}$ de $k$ en base $p$ est strictement plus grand que le chiffre correspondant $n_{i}$ de $n$, auquel cas ${\binom {n_{i}}{k_{i}}}=0$ . Ce corollaire est aussi un corollaire du théorème de Kummer.

Démonstration utilisant la formule du binôme

Cette démonstration est due à Nathan Fine qui l'a publiée en 1947.

Si $p$ est un nombre premier, la formule du pion montre que ${\binom {p}{k}}$ est multiple de $p$ pour $1\leqslant k\leqslant n$ et que donc

$(1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.$

Par récurrence, on en déduit que pour tout entier naturel $i$ :

$(1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.$

Connaissant $n=\sum _{i=0}^{r}n_{i}p^{i}$ et $k=\sum _{i=0}^{r}k_{i}p^{i}$, on peut écrire :

${\begin{aligned}\sum _{k=0}^{n}{\binom {n}{k}}X^{k}&=(1+X)^{n}=\prod _{i=0}^{r}\left((1+X)^{p^{i}}\right)^{n_{i}}\\&\equiv \prod _{i=0}^{r}\left(1+X^{p^{i}}\right)^{n_{i}}=\prod _{i=0}^{r}\left(\sum _{k_{i}=0}^{n_{i}}{\binom {n_{i}}{k_{i}}}X^{k_{i}p^{i}}\right)\\&=\prod _{i=0}^{r}\left(\sum _{k_{i}=0}^{p-1}{\binom {n_{i}}{k_{i}}}X^{k_{i}p^{i}}\right)=\sum _{k=0}^{n}\left(\prod _{i=0}^{r}{\binom {n_{i}}{k_{i}}}\right)X^{k}{\pmod {p}},\end{aligned}}$

D'où le résultat.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lucas' theorem » (voir la liste des auteurs).