Théorème de Lucas

Modèle:Autre4 En théorie des nombres, le théorème de Lucas exprime le reste de la division du coefficient binomial $(\genfrac{}{}{0ex}{}{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 :

$(\genfrac{}{}{0ex}{}{n}{k})\equiv \prod _{i=0}^r(\genfrac{}{}{0ex}{}{n_i}{k_i})(\mathrm{mod}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 $(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{p}{k})$ est multiple de $p$ pour $1⩽k⩽p-1$ et que donc

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

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

$(1+X{)}^{p^i}\equiv 1+X^{p^i}(\mathrm{mod}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{array}{cc}\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})X^k& =(1+X{)}^n=\prod _{i=0}^r{((1+X{)}^{p^i})}^{n_i}\\ & \equiv \prod _{i=0}^r{(1+X^{p^i})}^{n_i}=\prod _{i=0}^r\left(\sum _{k_i=0}^{n_i}(\genfrac{}{}{0ex}{}{n_i}{k_i})X^{k_i{p}^i}\right)\\ & =\prod _{i=0}^r\left(\sum _{k_i=0}^{p-1}(\genfrac{}{}{0ex}{}{n_i}{k_i})X^{k_i{p}^i}\right)=\sum _{k=0}^n\left(\prod _{i=0}^r(\genfrac{}{}{0ex}{}{n_i}{k_i})\right)X^k(\mathrm{mod}p),\end{array}$

D'où le résultat.