Théorème de Kummer (coefficients binomiaux)

En mathématiques, le théorème de Kummer donne une formule pour calculer le plus grand exposant d'une puissance d'un nombre premier divisant un coefficient binomial donné. En d'autres termes, il donne la valuation p-adique d'un coefficient binomial. Le théorème porte le nom d'Ernst Kummer, qui l'a démontré dans un article de 1852 .

Énoncé

Le théorème de Kummer stipule que pour des entiers donnés $n\geqslant k\geqslant 0$ et un nombre premier $p$, la valuation p-adique $v_{p}\left({\tbinom {n}{k}}\right)$ est égale au nombre de retenues effectuées lors de l'addition de $k$ et $l=n-k$ en base p.

Une formulation équivalente du théorème est la suivante :

Le développement de l'entier $n$ en base $p$ étant $n_{0}+n_{1}p+n_{2}p^{2}+\cdots +n_{r}p^{r}$, soit $s_{p}(n)=n_{0}+n_{1}+\cdots +n_{r}$ la somme de ses chiffres. Alors

$v_{p}\left({\binom {n}{k}}\right)={\dfrac {s_{p}(k)+s_{p}(l)-s_{p}(n)}{p-1}}.$

Cette dernière expression s'obtient en écrivant ${\tbinom {n}{k}}$ sous la forme ${\tfrac {n!}{k!\,l!}}$ et en utilisant la formule de Legendre: $v_{p}(n!)={\tfrac {n-s_{p}(n)}{p-1}}$.

Exemples

Pour calculer la plus grande puissance de 2 en divisant le coefficient binomial ${\tbinom {10}{3}}$ on écrit k = 3 et l = n − k = 7 en base p = 2 : 3 = 11₂ et 7 = 111₂ . Réaliser l'addition 11₂ + 111₂ = 1010₂ en base 2 nécessitant trois retenues, la plus grande puissance de 2 qui divise ${\tbinom {10}{3}}=120=2^{3}\cdot 15$ est 2³ .

Avec la deuxième expression, comme $s_{2}(3)=1+1=2$, $s_{2}(7)=1+1+1=3$, et $s_{2}(10)=1+0+1+0=2$, on obtient :

$v_{2}\left({\binom {10}{3}}\right)={\dfrac {s_{2}(3)+s_{2}(7)-s_{2}(10)}{2-1}}={\dfrac {2+3-2}{2-1}}=3.$

Applications

On déduit de la première forme du théorème que ${\tbinom {n}{k}}$ est non multiple de $p$ si et seulement si la somme de deux chiffres de même rang dans les expressions en base $p$ de $k$ et $l=n-k$ ne dépasse jamais $p-1$.

De manière équivalente, ${\tbinom {n}{k}}$ est multiple de $p$ si et seulement si au moins un chiffre de $k$ en base p est strictement plus grand que le chiffre correspondant de $n$.

En particulier, $\textstyle {n \choose k}$ est impair si et seulement si les expressions binaires de $k$ et $l=n-k$ ne présentent jamais deux 1 au même rang.

Si $\textstyle {n \choose k}$ est pair, $n$ possède donc forcément un chiffre binaire égal à 0, et par contraposée, si $n$ a tous ses chiffres égaux à 1, autrement dit si $n=2^{m}-1$, tous les $\textstyle {n \choose k}$ sont impairs.

Généralisation aux coefficients multinomiaux

Le théorème de Kummer peut être généralisé aux coefficients multinomiaux ${\tbinom {n}{k_{1},\ldots ,k_{m}}}={\tfrac {n!}{k_{1}!\cdots k_{m}!}}$ comme suit :

$v_{p}\left({\binom {n}{k_{1},\ldots ,k_{m}}}\right)={\dfrac {1}{p-1}}\left({\Bigl (}\sum _{i=1}^{m}s_{p}(k_{i}){\Bigr )}-s_{p}(n)\right).$

Voir aussi

• Théorème de Lucas

Références

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