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^[1] .

Énoncé

Le théorème de Kummer stipule que pour des entiers donnés $n ⩾ k ⩾ 0$ et un nombre premier $p$ , la valuation p-adique $v_{p} ((\binom{n}{k}))$ 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} + \dots + n_{r} p^{r}$ , soit $s_{p} (n) = n_{0} + n_{1} + \dots + n_{r}$ la somme de ses chiffres. Alors

v_{p} ((\binom{n}{k})) = \frac{s_{p} (k) + s_{p} (l) - s_{p} (n)}{p - 1} .

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

Exemples

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

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} ((\binom{10}{3})) = \frac{s_{2} (3) + s_{2} (7) - s_{2} (10)}{2 - 1} = \frac{2 + 3 - 2}{2 - 1} = 3.

Applications

On déduit de la première forme du théorème que $(\binom{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, $(\binom{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, $(\binom{n}{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 $(\binom{n}{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 $(\binom{n}{k})$ sont impairs.

Généralisation aux coefficients multinomiaux

Le théorème de Kummer peut être généralisé aux coefficients multinomiaux $(\binom{n}{k_{1}, \dots, k_{m}}) = \frac{n!}{k_{1}! \dots k_{m}!}$ comme suit :

v_{p} ((\binom{n}{k_{1}, \dots, k_{m}})) = \frac{1}{p - 1} ((\sum_{i = 1}^{m} s_{p} (k_{i})) - s_{p} (n)) .

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).

↑ (de) Ernst Kummer, « Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen », Journal für die reine und angewandte Mathematik, vol. 1852, n^o 44,‎ 1852, p. 93–146 (DOI 10.1515/crll.1852.44.93, lire en ligne)
↑ Mihet, « Legendre’s and Kummer’s Theorems Again », Resonance, vol. 15, n^o 12,‎ décembre 2010, p. 1111-1121 (lire en ligne)

Arithmétique et théorie des nombres

[1] (de) Ernst Kummer, « Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen », Journal für die reine und angewandte Mathematik, vol. 1852, n^o 44,‎ 1852, p. 93–146 (DOI 10.1515/crll.1852.44.93, lire en ligne)

[2] Mihet, « Legendre’s and Kummer’s Theorems Again », Resonance, vol. 15, n^o 12,‎ décembre 2010, p. 1111-1121 (lire en ligne)

[1]

[2]