Divisible par 720=6!

Tyoussef

Bonjour ou bonsoir (voir l'heure)

Montrer que pour tout entier $n$, l’entier

$$ N = n\times (n+1) \times (n+2) \times (n+3)\times (n+4)\times (n+5)$$ est divisible par $720$.
Merci d'avance.

Math Coss

Évident : $N=6!\dbinom{n+5}{6}$.

DeGeer

Tu peux voir que $N$ est divisible par 6 et par 5 puis utiliser les congruences pour les autres diviseurs.

Math Coss

Ça ne suffit pas car la valuation de $2$ et $3$ dans $6!$ est $>1$. Vérifier que $N$ est divisible par $2$ et $3$ après avoir vérifié que c'est divisible par $6$ est doublement inutile : c'est évident et ça n'apporte rien pour la divisibilité par $6\times2\times3=36$. Même problème avec $4$ vis à vis de ce même $36$.

Math Coss

Cela dit, on en tire tout de même une méthode de démonstration : il suffit de vérifier la divisibilité par $16$ pour $n=0,\dots,15$, par $9$ pour $n=0,\dots,8$ et par $5$ pour $n=0,\dots,4$. \[\begin{array}{c|c|c|c|c|c|c|c|c}n&0&1&2&3&4&5&6&7\\ N&0&720&5040&20160&60480&151200&332640&665280\\\hline n&8&9&10&11&12&13&14&15\\ N&1235520&2162160&3603600&5765760&8910720&13366080&19535040&27907200\end{array}\]La divisibilité par $16$ se teste sur les cinq derniers chiffres (car $10000=16\times625$), par $9$ sur la somme des chiffres, par $5$ en examinant le dernier chiffre.

NicoLeProf

Bonjour à toi, merci beaucoup pour ce très joli exercice d'arithmétique !

J'adore tes posts @Tyoussef (je suis fan d'arithmétique !!! ) donc j'y réponds avec plaisir !

Ce n'est peut-être pas la méthode la plus rapide mais voici ce que je te propose :

tu remarques que $720=6!=6 \times 5 \times 4 \times 3 \times 2=2^4 \times 3^2 \times 5$ (en décomposant en produit de facteurs premiers).

Maintenant, l'objectif serait de :

1) Montrer que $N$ est divisible par $5$ (en raisonnant modulo $5$ ou en remarquant que tu as un produit d'un certain nombre d'entiers consécutifs : je te laisse justifier) ;

2) Montrer que $N$ est divisible par $3^2=9$ (en raisonnant modulo $9$ ou en faisant deux groupes astucieux: chacun multiple de $3$) ;

3) Montrer que $N$ est divisible par $16=2^4$ (c'est le plus compliqué, une indication : prouve d'abord que $n(n+1)(n+2)(n+3)$ est multiple de $8$) ;

4) Conclure en expliquant pourquoi ! 

Tu peux y arriver maintenant !!!

Tyoussef

Bonsoir tout le monde.
En fait je voulais poser mon idée, mais j'ai reçu un coup de téléphone.

Tyoussef

@ Math Coss

En fait le $6!$, c'est moi qui l'ajouté. J'ai remarqué que le nombre $N$, une sorte de translation de $6!$

Et je me suis dit : $\ 6!\mid N $ alors : $\quad
\left\{
        \begin{array}{ll}
      A^{n-1}_{n+5}  = (n+5)(n+4) (n+3) (n+2)(n+1)n \\
      A^{n-1}_{n+5}  = \frac{(n+5)!}{((n+5)-(n+1))!} = \frac{(n+5)!}{6!} 
        \end{array}
    \right.
$

Ouuups le $6!$ est au mauvais endroit. Et lorsque j'ai vu votre réponse     Math Coss  je sais que j'ai fait une erreur quelque part.

Tyoussef

:@ Math Coss
Très bien vu,  voilà l'idée, que je cherche : $\quad A^{6}_{n+5} = 6! C ^{6}_{n+5} $,
donc :  $ 6! \mid  A^{6}_{n+5} $.

  combinatoire et arithmétique.   Merci Math Coss

Tyoussef

@ NicoLeProf
Merci, avec plaisir NicoLeProf.
J'aime bien comment vous avez vu le problème. Comme je l'ai déjà dit le $6!$, c'est moi qui l'ajoute dans le problème, on a posé 720.

$$
\left\{
        \begin{array}{ll}
      16 \mid N \\
       9 \mid N \\
       5 \mid N 
        \end{array}
    \right.\quad \Longrightarrow \quad  ppcm(16,5,9)  \mid N
$$ car : $16, 5 $ et $9$  sont premier entre eux.
Or : $\  ppcm(16,5,9) = 720  $.

On obtient $\quad\boxed{ 720 \mid N  }.$

DeGeer

En fait,  mon idée était que l'un des facteurs de $N$ était divisible par $6$, un autre par $3$, un autre par $2$ et encore un autre par $4$, donc que $N$ est divisible par $2 \times 3 \times 4 \times 6$, ainsi que par $5$ qui lui est premier, donc est divisible par $6!$.

lourrran

L'argument $A^{6}_{n+5} = 6! C ^{6}_{n+5}$ donc $6! \mid  A^{6}_{n+5}$ me semble un argument circulaire.

Math Coss

@DeGeer : Dit comme ça, ça devient crédible. Encore que je ne vois pas bien l'argument pour $2$ et ses multiples. Comment être sûr que le multiple de $6$ (nécessairement unique) n'est pas le multiple de $4$ (il y en a un ou deux) ? Pour prendre un exemple, $n=10$. Parmi $10$, $11$, $12$, $13$, $14$, $15$, le seul multiple de $4$ est aussi le multiple de $6$.

Je dirais ça : parmi les six nombres consécutifs, il y a au moins deux multiples de $2$ et un multiple de $4$ (éventuellement l'inverse) ; il y a au moins deux multiples de $3$ ; au moins un multiple de $5$ ; le produit est donc divisible par $2^2\times4\times3^2\times5$.

@lourrran : éventuellement mais pas nécessairement. Voici ce qu'on peut dire sans circularité. Pour $m\ge6$, on note $I_m$ le nombre d'injections de $\{1,\dots,6\}$ dans $\{1,\dots,m\}$. On se convainc que $|I_m|=m(m-1)(m-2)(m-3)(m-4)(m-5)$ (« par récurrence sur $6$... »). Par ailleurs, en termes snobs, le groupe $\mathfrak{S}_6$ opère (à droite) sur l'ensemble $I_m$ : si $f$ est un arrangement et $\sigma\in\mathfrak{S}_6$, $\sigma\cdot f=f\circ\sigma$ est encore un arrangement ; cette action est libre car si $f\circ\sigma=f$, on voit que $\sigma$ est l'identité grâce à l'injectivité de $f$. Les orbites ont donc toutes pour cardinal $6!$, nombre qui divise donc $|I_m|$.

De façon plus terre à terre, on associe à $f\in I_m$ son image $\{f(1),\dots,f(6)\}$, ce qui définit une application $\varphi$ de $I_m$ vers l'ensemble $P_m$ des parties à $6$ éléments de $\{1,\dots,m\}$ (six éléments parce que $f$ est injective). On se convainc que $\varphi(f)=\varphi(g)$ SSI il existe $\sigma\in\mathfrak{S}_6$ tel que $g=f\circ\sigma$ (même orbite pour l'action précédente) et que si $\sigma\ne\tau$, alors $f\circ\sigma\ne f\circ\tau$. Autrement dit, tout élément de $P_m$ admet exactement $6!$ antécédents. Par le lemme des bergers, $|I_m|=6!|P_m|$, ce qui donne la divisibilité cherchée (parce qu'on sait que $|P_m|$ est un entier !) et en prime la formule habituelle pour le coefficient binomial $\binom{m}6=|P_m|$.

Bien sûr, plus haut, l'expression « par récurrence sur $6$ » est une boutade. Ce qu'il faut dénombrer, c'est $\mathsf{A}_n^p$ pour $p\le n$ par récurrence finie sur $p$.

kioups

On peut aussi montrer que tout produit de $n$ entiers naturels consécutifs est divisible par $n!$. Une double récurrence bien sympathique, si je me souviens bien.

Math Coss

Une bonne façon pour montrer que le produit de $p$ entiers consécutifs est divisible par $p!$ me semble être, en deux temps, le dénombrement du nombre $\mathsf{A}_n^p$ de $p$-arrangements (ici, si on veut, on peut mettre une double récurrence, ou plutôt une récurrence finie dans une récurrence normale) et le lemme des bergers pour l'application qui envoie un arrangement sur son image.

En fait, c'est ce que j'ai écrit dans ce message dont l'essentiel a été posté après celui de @kioups, malgré les apparences.

gebrane

Tyoussef

@ DeGeer
Oui, j'ai compris votre idée, belle remarque.

Tyoussef

Azol gebrane (Azol veut dire bonjour dans ma langue natale.)
je n'arrive pas à vous suivre comme d'habitude .
Le $B_{n,k }$ c'est la factorielle ??

gebrane

Pourquoi penses-tu que c'est factorielle ?

Dom

J’avais compris ce truc là assez tôt (collège) mais je n’avais pas réussi à le démontrer.  

C’est pourtant « évident » que les multiples de 2, de 3, de 4, etc. se suivent… on « voit » bien que ça marche.  

Soc

Pas si évident puisque c'est faux, comme soulevé par Math Coss. Tu auras bien un multiple de chaque, mais tu peux compter deux fois le même.

NicoLeProf

Pourquoi une récurrence pour $\mathscr{B}_{k,n}$ ici, n'a-t-on pas : $(k+1)! \displaystyle \binom{n+k+1}{k+1}=(n+1)...(n+k+1)$ ?

Soc

Pour faire une démonstration avec les mains, plutôt que de chercher les entiers, on cherche les facteurs premiers (un peu comme avec Lebesgue, on compte les lignes plutôt que les colonnes).

Il y a autant de 2 dans k! que de multiples de 2 dans k... ou presque car certains multiples contiennent plusieurs 2.
Les multiples de 2 qui contiennent plusieurs 2 sont les multiples de 4, donc il faut ajouter autant de 2 qu'il y a de multiples de 4...
Et l'on recommence pour les multiples de 8, 16, 32 etc...
Puis l'on recommence avec les multiples de 3,9,27 etc...
Il nous reste à comprendre que l'on pourra retrouver tous ces facteurs dans [n+,n+k]:

Il y aura au moins autant de multiples de 2 dans [n+1,n+k] que dans [1,k]. On extrait un 2 pour chaque.
Il y aura au moins autant de multiples de 4 dans [n+1,n+k] que dans [1,k]. On extrait un 2 pour chaque.
Il y aura au moins autant de multiples de 8 dans [n+1,n+k] que dans [1,k]. On extrait un 2 pour chaque.
etc...

Puis on recommence avec 3,9,27 etc...

On va ainsi bien recomposer k! en prenant les facteurs dans [n+1,n+k].

Dom

Bien entendu que le « on voit » ou le « c’est évident » manque de rigueur. 

Je tente une explication (avec encore une fois les gants qu’il faut pour dire que ce n’est pas une preuve). 

On prend six nombres consécutifs, c’est le cas particulier du fil. 

A,B,C,D,E,F
Dedans, j’ai forcément un multiple de 6 et un
seul. 

Puis j’ai forcément un multiple de 5 (peut-être deux selon sa place mais en fait peu importe, car 5 est premier avec tout le reste). 

Les multiples de 2, ils sont au nombre de trois (soit ACE, soit BDF). 

Puis les multiples de 4… soit deux… soit un seul…
Et en passant en revue toutes les possibilités on a même presque une preuve. 

J’en reparle plus tard. 

gebrane

NicoLeProf a dit :

Pourquoi une récurrence pour $\mathscr{B}_{k,n}$ ici, n'a-t-on pas : $(k+1)! \displaystyle \binom{n+k+1}{k+1}=(n+1)...(n+k+1)$ ?

Nico, si tu veux utiliser les coefficients binomiaux, tu n'as qu'à les utiliser dès le début, puisque $(n+1)(n+2)...(n+k)=k!\binom{n+k}{k}$. Mais la subtilité réside dans la démonstration que $\binom{n+k}{k}$ est un entier. Tu dois partir de la définition selon laquelle $\binom{p}{k}$ désigne le nombre de parties de k éléments parmi p. Cette définition conduit à un entier naturel. Cependant, il est également nécessaire d'établir la formule $\binom{p}{k}=p!/k!(p-k)!$. Pour éviter tout cela, nous pouvons utiliser une récurrence double, comme recommandé dans les messages précédents.

NicoLeProf

Ok je vois merci gebrane ! Oui j'ai supposé connue la formule des coefficients binomiaux avec les factorielles ! ^^'

gebrane

Alors termine le raisonnement sans faire appel aux coefficients binomiaux, mon crayon est cassé (ce n'est pas difficile)

NicoLeProf

En effet, pas hyper dur mais il faut s'y pencher un peu : ici, raisonner de tête avec des petites valeurs de $n$ permet de voir comment on peut passer de $n$ à $n+1$ . Je pense avoir trouvé : 

je rédige rapidement : je considère donc le produit $(n+2)...(n+k+1)(n+k+2)$ et je l'écris comme ceci : $(n+2)...(n+k+2)=(n+2)...(n+k+1)(n+1)+(n+2)...(n+k+1)(k+1)$ .

Par l'hypothèse de récurrence $\mathscr{B}_{k,n}$, $(n+2)...(n+k+1)(n+1)$ est divisible par $(k+1)!$ .

Pour l'autre terme, on utilise l'hypothèse de récurrence $\mathscr{A}_k$ qui permet d'affirmer que $(n+2)...(n+k+1)$ est divisible par $k!$ donc $(n+2)...(n+k+1)(k+1)$ est divisible par $(k+1)!$ .

Ainsi, $\mathscr{B}_{k,n+1}$ est vraie ! Ce qui permet de conclure.  

P.S. : j'adore l'excuse du "crayon cassé" !

gebrane

Bien vu

Soc

Ma solution n'a pas l'air de vous plaire, mais elle a le mérite de passer pour des élèves de collège que l'on a un peu familiarisés avec les nombres premiers, et avec le nombre de fois qu'apparait un facteur premier, par exemple en leur demandant le nombre de 0 à la fin de 50!

gebrane

Soc

Au contraire ta méthode me plait bien et par les mêmes raisons que tu as cité, mais j'ai voulu répondre implicitement au message de Mathcoss

Math Coss a dit :

Une bonne façon pour montrer que le produit de $p$ entiers consécutifs est divisible par $p!$ me semble être, en deux temps, le dénombrement du nombre $\mathsf{A}_n^p$ de $p$-arrangements (ici, si on veut, on peut mettre une double récurrence, ou plutôt une récurrence finie dans une récurrence normale) et le lemme des bergers ...

La méthode que j'ai mentionnée utilise une récurrence double et ne nécessite pas le lemme des bergers