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 ${\displaystyle {\tbinom {n}{k}}}$ par un nombre premier ${\displaystyle p}$ en termes du développement en base ${\displaystyle p}$ des entiers ${\displaystyle n}$ et ${\displaystyle k}$.

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

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

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

où

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

et

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

sont les développements respectifs de ${\displaystyle n}$ et ${\displaystyle k}$ en base ${\displaystyle p}$.

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

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

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

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

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

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

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

${\displaystyle {\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.

• Arithmétique et théorie des nombres