(n+1)(n+2)…(n+k) est multiple de k!

1 – Introduction

Le problème suivant a été soumis aux élèves d’une classe de troisième :

Prouver que la somme de cinq entiers consécutifs est multiple de 5.

Ce n’est pas bien difficile : en notant ces cinq entiers n-2, n-1, n, n+1 et n+2, leur somme est égale à 5n, ce qui règle la question.

On peut d’ailleurs généraliser en remplaçant 5 par n’importe quel entier naturel impair :

Proposition 1

Pour tout p\in\mathbb{N}, la somme de 2p+1 entiers consécutifs est multiple de 2p+1.

En effet, si l’on note k+i ces entiers, avec -p\leqslant i\leqslant p et k\in\mathbb{Z}, on constate que :

    \[ \sum_{i=-p}^{p}\left(k+i\right)=\left(2p+1\right)k \]

Notons que ça ne marche pas avec un nombre pair de termes !

Par exemple : 1 + 2 + 3 + 4 = 10 n’est pas multiple de 4.

Maintenant, si l’on remplace somme par produit, les choses vont devenir plus intéressantes.

Quel pourrait être l’énoncé analogue pour un produit d’entiers consécutifs ? Observons un peu avant de nous lancer…

  • Le produit de deux entiers consécutifs est pair, car l’un des deux facteurs l’est !
  • Le produit de trois entiers consécutifs est multiple de 3, puisque – là encore – l’un des trois facteurs l’est.

Il est clair que ceci se généralise, pour donner :

Proposition 2

Pour tout entier k\geqslant1, le produit de k entiers consécutifs est multiple de k.

On trouve en effet, parmi k entiers consécutifs, un multiple de k (et un seul, d’ailleurs).

Mais on peut obtenir bien mieux ! Nous allons démontrer de plusieurs façons le :

Théorème (T)

Pour tout entier k\geqslant1, le produit de k entiers consécutifs est multiple de k!

➡ Pour k = 1, l’affirmation est triviale.

➡ Pour k = 2, on affirme que le produit de deux entiers consécutifs est pair.

➡ Pour k = 3, il y a du nouveau : le théorème stipule que le produit de trois entiers consécutifs est multiple de 3! = 6. Ceci s’explique aisément : un tel produit est multiple de 2 et de 3, donc de 6 puisque 2 et 3 sont premiers entre eux.

Etant donnés des entiers a,b et c tels que c soit multiple de a et de b, il ne faut pas conclure hâtivement que c est multiple du produit ab, car c’est en général faux ! Par exemple :

12 est multiple de 4 et de 6, mais 12 n’est pas multiple de 24.

Cependant :

Proposition 3

Si a et b sont premiers entre eux et si c est multiple de a et de b, alors c est multiple de ab.

Preuve (cliquer pour déplier / replier)

Comme a et b sont premiers entre eux, il existe des entiers p et q tels que pa+qb=1 (identité de Bézout). Il s’ensuit que c=pac+qbc.

Or, il existe par hypothèse des entiers k,\ell tels que c=ka=b\ell.

Ainsi : c=pab\ell+qbka=ab\left(p\ell+qk\right). On a bien montré que c est multiple de ab.

➡ Voici un autre point de vue …

Comme c est multiple de a et de b, alors c est multiple de m=PPCM\left(a,b\right). Or, (propriété générale) en notant d=PGCD\left(a,b\right), on a : md=ab. Vu que d=1, cette dernière égalité devient m=ab, ce qui donne la conclusion.

Examinons encore un cas particulier du théorème (T), celui où k = 4.

Il s’agit de comprendre pourquoi le produit de quatre entiers consécutifs est multiple de 24.

Comme 24 = 3 \times 8 et vu que 3 et 8 sont premiers entre eux, il suffit (d’après la proposition 3 ci-dessus) de vérifier que ce produit est multiple de 3 et de 8.

➡ Le fait qu’il soit multiple de 3 a déjà été expliqué.

➡ Par ailleurs, ce produit comporte deux facteurs pairs qui sont respectivement de la forme 4q et et 4q\pm2, il est donc clairement multiple de 8.

L’examen du cas k = 5 est laissé en exercice, pour le lecteur intéressé 😉

Il est temps d’aborder la preuve du théorème (T) dans le cas général.

Nous pouvons nous limiter à des entiers naturels consécutifs. Il ne s’agit pas là d’une restriction, puisque si l’un de ces k entiers consécutifs est nul, alors leur produit aussi (et 0 est bien multiple de k!) et s’ils sont tous négatifs, alors leur produit vaut \left(-1\right)^{k}A,A est le produit de k entiers consécutifs positifs.

Trois preuves du théorème (T) sont proposées dans les sections suivantes. 

2 – Une preuve combinatoire

  Si l’on connaît les coefficients binomiaux, on ne peut pas s’empêcher d’observer qu’en notant N=\left(n+1\right)\left(n+2\right)\cdots\left(n+k\right) et D=1\times 2\times \cdots\times k = k!, on obtient :

    \[ \frac{N}{D}=\frac{\left(n+k\right)!}{k!\thinspace n!}=\binom{n+k}{k} \]

qui est un entier naturel. Fin de l’histoire.

Pour que l’explication soit complète, il faut bien sûr rappeler que si deux entiers naturels p et k vérifient k\leqslant p, alors \binom{p}{k} désigne par définition le nombre de parties de cardinal k d’un ensemble de cardinal p (et c’est donc évidemment un entier naturel). Mais ce n’est pas tout, car il faut aussi établir la formule (dite de Fermat) selon laquelle :

    \[\binom{p}{k}=\frac{p!}{k!\thinspace\left(p-k\right)!}\]

Tout ceci est expliqué en détail dans cet article sur les coefficients binomiaux, auquel vous pourrez vous reporter si nécessaire. 

3 – Une preuve arithmétique

Dans ce qui suit, nous utiliserons le théorème fondamental de l’arithmétique, selon lequel tout entier n supérieur ou égal à 2 se décompose en produit de nombres premiers, sous la forme :

    \[ n=p_{1}^{\alpha_{1}}\cdots p_{r}^{\alpha_{r}} \]

avec p_{1},\cdots,p_{r} premiers distincts et \alpha_{1},\cdots,\alpha_{r} entiers naturels non nuls.

En outre, cette décomposition en facteurs premiers (ou DFP) est unique (à l’ordre près des facteurs).

Si p est un diviseur premier de n, l’exposant de p dans la DFP de n est appelé “valuation p-adique de n” et noté v_{p}\left(n\right).

Et si le nombre premier p n’est pas un diviseur de n, on convient que v_{p}\left(n\right)=0.

Avec cette définition, il est facile de prouver que :

    \[\boxed{v_{p}\left(mn\right)=v_{p}\left(m\right)+v_{p}\left(n\right)}\]

pour tout couple \left(m,n\right) d’entiers naturels non nuls et pour tout nombre premier p.

Voici maintenant le principe sur lequel repose notre preuve arithmétique du théorème (T) :

Principe :

Etant donnés des entiers naturels non nuls N et D, il suffit pour montrer qu’une fraction \frac{N}{D} représente un nombre entier, de prouver que pour tout p premier :

    \[v_{p}\left(D\right)\leqslant v_{p}\left(N\right)\]

Dans le cas qui nous intéresse :

    \[\frac{N}{D}=\frac{\left(n+1\right)\cdots\left(n+k\right)}{k!}=\frac{\left(n+k\right)!}{k!\thinspace n!}\]

Il suffit donc de prouver que, pour tout p premier :

    \[ v_{p}\left(k!\right)+v_{p}\left(n!\right)\leqslant v_{p}\left(\left(n+k\right)!\right)\qquad\left(\star\right)\]

C’est là qu’intervient la formule de Legendre, qui donne la valuation p-adique d’une factorielle :

Théorème (Formule de Legendre)

Si n\in\mathbb{N}^{\star} et p\in\mathbb{P}, alors :

    \[v_{p}\left(n!\right)=\sum_{j=1}^{\infty}\left\lfloor \frac{n}{p^{j}}\right\rfloor\]

La partie entière de \frac{n}{p^{j}} étant nulle dès que p est assez grand, la somme ci-dessus est finie (contrairement aux apparences).

Pour ceux que ça intéresse, une preuve de cette célèbre formule est donnée en annexe.

Avec cette relation en poche, on voit que :

    \[ v_{p}\left(\left(n+k\right)!\right)-v_{p}\left(k!\right)-v_{p}\left(n!\right)=\sum_{p=1}^{\infty}\left(\left\lfloor \frac{n+k}{p^{j}}\right\rfloor -\left\lfloor \frac{n}{p^{j}}\right\rfloor -\left\lfloor \frac{k}{p^{j}}\right\rfloor \right) \]

Or, pour tout couple \left(x,y\right) de nombres réels, on a :

    \[ \left\lfloor x\right\rfloor \leqslant x\qquad\text{et}\qquad\left\lfloor y\right\rfloor \leqslant y \]

d’où :

    \[ \left\lfloor x\right\rfloor +\left\lfloor y\right\rfloor \leqslant x+y \]

et donc, par définition de la partie entière de x+y :

    \[ \left\lfloor x\right\rfloor +\left\lfloor y\right\rfloor \leqslant\left\lfloor x+y\right\rfloor \]

L’inégalité \left(\star\right) en résulte. 

4 – Une preuve par double récurrence

Le lecteur peu familier avec la méthode de démonstration par récurrence pourra consulter l’article Qu’est-ce qu’une preuve par récurrence ?

Prouvons que l’assertion :

\mathcal{A}_{k} : “le produit de k entiers naturels consécutifs est multiple de k!

est vraie pour tout k\geqslant1.

➡ D’évidence, \mathcal{A}_{1} est vraie.

➡ Supposons \mathcal{A}_{k} vraie pour un certain k\geqslant1 et montrons que \mathcal{A}_{k+1} est vraie. Pour cela, montrons par récurrence sur n que l’assertion

\mathcal{B}_{k,n} : “\left(n+1\right)\cdots\left(n+k+1\right) est multiple de \left(k+1\right)!

est vraie pour tout n\in\mathbb{N}.

➡➡ D’évidence, \mathcal{B}_{k,0} est vraie.

➡➡ Supposons \mathcal{B}_{k,n} vraie pour un certain n\in\mathbb{N}. Autrement dit :

    \[\left(n+1\right)\cdots\left(n+k+1\right)=\lambda\left(k+1\right)!\qquad\text{avec }\lambda\in\mathbb{N}\]

On constate, en posant A=\left(n+2\right)\cdots\left(n+k+1\right), que :

    \begin{eqnarray*}\left(n+2\right)\cdots\left(n+k+2\right) & = & \left(n+2\right)\cdots\left(n+k+1\right)\left[\left(n+1\right)+\left(k+1\right)\right]\\ & = & \left(n+1\right)\cdots\left(n+k+1\right)+\left(k+1\right)A\\ & = & \lambda\left(k+1\right)!+\left(k+1\right)A \end{eqnarray*}

Comme A est le produit de k entiers consécutifs, c’est un multiple de k! d’après \mathcal{A}_{k}. Ainsi \left(n+2\right)\cdots\left(n+k+2\right) est multiple de \left(k+1\right)! autrement dit \mathcal{B}_{k,n+1} est vraie.

On a montré que \mathcal{A}_{k+1} est vraie et le tour est donc joué. Au passage, c’est un joli exemple de deux récurrences emboîtés.

5 – Que dire de plus ?

Nous avons établi de trois façons que, pour tout entier k\geqslant1, le produit de k entiers consécutifs est nécessairement multiple de la factorielle de k. Ce résultat constitue une amélioration substantielle de la proposition 2 énoncée dans l’introduction. Peut-il être encore amélioré ?

Voici deux pistes de réflexion :

Piste 1

Trouver, si possible, un diviseur non trivial de \left(n+1\right)\cdots\left(n+k\right) qui soit plus “gros” que la factorielle de k. Cette question ne semble pas facile.

Piste 2

Trouver en fonction de k et q une estimation de n_{k,q} = le plus petit n pour lequel \left(n+1\right)\cdots\left(n+k\right) est divisible par q! (avec q>k donné).

Je m’explique : pour 1\leqslant q\leqslant k, la question n’a aucun intérêt puisque tout entier n\geqslant1 convient (c’est ce que dit notre théorème (T)).

Pour q=k+1, il est clair que n=1 convient.

Dès que q>k+1, les choses cessent d’être simples, mais un tel n existe (puisque n=q!-1 convient), ce qui rend licite la définition de n_{k,q}.

Le tableau ci-dessus donne les valeurs de n_{k,q} pour quelques couples \left(k,q\right) : Par exemple, le fait que n_{5,10}=347 signifie que le produit

    \[ 348\times349\times350\times351\times352 \]

est multiple de 10!=3628800 et que ce n’est le cas d’aucun produit \left(n+1\right)\left(n+2\right)\left(n+3\right)\left(n+4\right)\left(n+5\right) pour 0\leqslant n\leqslant346.

Citons pour finir un résultat difficile, publié en 1974 par Paul Erdös et John Selfridge (consultable ici) :

Le produit d’au moins deux entiers naturels non nuls consécutifs n’est jamais une puissance parfaite (c’est-à-dire : n’est jamais de la forme N^{r} avec r\geqslant2 et N\in\mathbb{N}).

Annexe – une preuve de la formule de Legendre

Commençons par un mini-exercice de dénombrement.

Exercice

Etant donnés deux entiers naturels non nuls n et q, combien existe-t-il d’entiers compris (au sens large) entre 1 et n qui sont multiples de q ?

Ces entiers sont les \lambda q, avec 1\leqslant\lambda\leqslant\frac{n}{q}; la réponse est donc immédiate : il en existe \left\lfloor \frac{n}{q}\right\rfloor .

Par exemple, les multiples de 23 compris entre 1 et 7654 sont au nombre de \left\lfloor \frac{7654}{23}\right\rfloor =332.

A présent, venons-en à la preuve de la formule de Legendre. Les entiers compris entre 1 et n peuvent être classés selon leur valuation p-adique.

Ceux dont la valuation p-adique est j (pour j\in\mathbb{N} donné) sont les multiples de p^{j} qui ne sont pas multiples de p^{j+1}. Ils sont donc au nombre de {\displaystyle \left\lfloor \frac{n}{p^{j}}\right\rfloor -\left\lfloor \frac{n}{p^{j+1}}\right\rfloor .}

En notant E_{j} leur ensemble, on observe que :

    \[ \left\{ 1,\cdots,n\right\} =\bigsqcup_{j\geqslant0}E_{j} \]

Bien entendu E_{j}=\emptyset pour j assez grand et cette union disjointe est donc finie !

Plus précisément, E_{j} est vide dès que j>n. En effet, si 1\leqslant a\leqslant n et v_{p}\left(a\right)>n, alors :

    \[a\geqslant p^{v_{p}\left(a\right)}>p^{n}\geqslant2^{n}>n\]

ce qui est absurde !

On utilise ensuite le fait que la valuation p-adique d’un produit est la somme des valuations p-adiques des différents facteurs :

    \[ v_{p}\left(n!\right)=\sum_{k=1}^{n}v_{p}\left(k\right)=\sum_{j\geqslant0}\sum_{k\in E_{j}}v_{p}\left(k\right)=\sum_{j\geqslant0}j\left(\left\lfloor \frac{n}{p^{j}}\right\rfloor -\left\lfloor \frac{n}{p^{j+1}}\right\rfloor \right)\]

Le premier terme de la somme est nul.

Quant aux suivants, ils se télescopent :

    \begin{eqnarray*}v_{p}\left(n!\right) & = & \sum_{j\geqslant1}j\left(\left\lfloor \frac{n}{p^{j}}\right\rfloor -\left\lfloor \frac{n}{p^{j+1}}\right\rfloor \right)\\& = & \sum_{j\geqslant1}\left\lfloor \frac{n}{p^{j}}\right\rfloor +\sum_{j\geqslant1}\left(\left(j-1\right)\left\lfloor \frac{n}{p^{j}}\right\rfloor -j\left\lfloor \frac{n}{p^{j+1}}\right\rfloor \right)\\& = & \sum_{j\geqslant1}\left\lfloor \frac{n}{p^{j}}\right\rfloor \end{eqnarray*}

ce qui achève la preuve.


Vos questions ou remarques seront toujours les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.

Partager cet article
  • 2
  •  
  •  
  •  

Cet article a 2 commentaires

  1. Joseph Cesana

    C’est un reel plaisir de lire et d’etudier vos articles… retour aux maths apres tant d’anne’es avec beaucoup d’enthousiasme.

    – Joseph Cesana

    1. René Adad

      Merci beaucoup Joseph !

Laisser un commentaire