Formule de n! par un produit de ppcm
$\newcommand{\ppcm}{\operatorname{ppcm}}$Bonjour, je souhaite montrer la formule suivante :
$$n!=\prod_{i=1}^{n}\ppcm\big(1,2,\ldots,E(\tfrac{n}{i})\big),$$
où $E$ est la partie entière.
On peut par exemple montrer que leurs décompositions primaires sont les mêmes. Par Legendre, on connaît les valuations $p$-adiques de $n!$. On a de plus :
$$v_p\Big(\prod_{i=1}^{n}\ppcm\big(1,2,\ldots,E(\tfrac{n}{i})\big)\Big) = \sum_{i=1}^{n}\max_{k \in \{1,\ldots,E(\tfrac{n}{i})\}} v_p(k).$$
Comment montrer que cette dernière somme est égale à la somme de Legendre de $n!$ ?
Je vous remercie.
$$n!=\prod_{i=1}^{n}\ppcm\big(1,2,\ldots,E(\tfrac{n}{i})\big),$$
où $E$ est la partie entière.
On peut par exemple montrer que leurs décompositions primaires sont les mêmes. Par Legendre, on connaît les valuations $p$-adiques de $n!$. On a de plus :
$$v_p\Big(\prod_{i=1}^{n}\ppcm\big(1,2,\ldots,E(\tfrac{n}{i})\big)\Big) = \sum_{i=1}^{n}\max_{k \in \{1,\ldots,E(\tfrac{n}{i})\}} v_p(k).$$
Comment montrer que cette dernière somme est égale à la somme de Legendre de $n!$ ?
Je vous remercie.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Séparer les $i$ qui divisent $n+1$ de ceux qui ne le divisent pas.
$(n+1)!=(n+1)n!$.
Cordialement
Paul.
\begin{align*}
\sum_{k=1}^n \log \left( \textrm{ppcm} \, \left(1, \dotsc, \left \lfloor \frac{n}{k} \right\rfloor \right) \right) &= \sum_{k=1}^n \sum_{d=1}^{\lfloor n/k \rfloor} \Lambda(d) \\
&= \sum_{d=1}^n \Lambda (d) \sum_{k=1}^{\lfloor n/d \rfloor} 1 \\
&= \sum_{d=1}^n \Lambda (d) \left \lfloor \frac{n}{d} \right \rfloor \\
&= \log (n!)
\end{align*}
où la dernière égalité provient de la sommation de l'identité de convolution $\Lambda \star \mathbf{1} = \log$. Il n'y a alors plus qu'à passer à l'exponentielle.
depasse, je ne comprends pas où vous voulez en venir. Pouvez-vous détailler un peu plus pour que je puisse voir de quoi il s'agit ? Je vous remercie.
Je pense que la première étape, c'est de vérifier par soi-même que l'égalité est exacte. Pour s'en imprégner.
Sur des petits nombres (par exemple $n=6$ ou $n=7$), calculer l'expression de droite, et vérifier que ça correspond à $n!$
Pour $n=6$, est ce que $6!=\ppcm(1,2,3,4,5,6)\times\ppcm(1,2,3)\times\ppcm(1,2)$
Pour $n=7$, est ce que $7!=\ppcm(1,2,3,4,5,6,7)\times\ppcm(1,2,3)\times\ppcm(1,2)$
Effectivement, ça marche.
On peut envisager une récurrence.
Quand on passe de 6 à 7, le nombre ajouté est premier, et là, c'est facile .... si la propriété est vraie pour $p-1$ (avec $p$ premier), elle est vraie pour $p$.
Mais quand on passe de 7 à 8, la récurrence se passe moins bien :
est-ce que $8!=\ppcm(1,2,3,4,5,6,7,8)\times\ppcm(1,2,3,4)\times\ppcm(1,2)\times\ppcm(1,2)$
Oui, ça colle, mais la récurrence semble difficile à exploiter.
On voit bien qu'entre le premier terme $\ppcm(1,2,3, \ldots, 8)$ et $8!$, on a les mêmes 8 facteurs. Et c'est juste une histoire de doubles-comptes qui fait la différence.
Et ces doubles comptes manquants, on les rattrape avec tous les autres facteurs.
On envisage alors une autre méthode.
On a 2 termes $A$ et $B$, et on veut montrer qu'ils sont égaux.
Il suffit pour ça de montrer que pour tout nombre premier $p$, $v_p(A)=v_p(B)$ : $A$ et $B$ ont la même décomposition en facteurs premiers.
Pour tous les nombres premiers $p>n$, c'est évident.
Pour tous les nombres premiers $p$ entre $n/2$ (exclu) et $n$, c'est évident aussi.
Puis les nombres premiers p tels que $n/3 < p \le n/2$ , ça se complique, mais ça paraît jouable etc etc
Je pense que la piste est bonne.
Dès lors, il n'y a pas plus simple que la preuve que j'ai exposée ci-dessus. Vu sa simplicité, il peut être intéressant d'investir un peu de temps dans les bases de la théorie analytique des nombres, non ?
De plus, la formule de Legendre est certes une belle formule, mais je doute qu'elle puisse être efficacement utile ici.
La suite des $P_n(:=\ppcm (1,2,\ldots,n))$ est strictement croissante et $P_{n+1} = p P_n$, où $p$ est un diviseur premier de $n+1$:
C'est une bêtise: $P_5=P_6$! Merci Marco!
Mes $P(n,i)$ et $P(n+1,i)$ sont égaux si et seulement si $i$ ne divise pas $n+1$.
Si $i$ divise $n+1$, $P(n+1,i)=p P(n,i)$, où $p$ est un diviseur premier de $n+1$.
Donc (!!!) $n+1$ est le produit des $\dfrac{P(n+1,i)}{P(n,i)}$.
Ce n'est pas une démonstration, c'est une idée.
Cordialement.
Paul.
Maintenant, si l'on ne veut pas de cette fonction,...
La démonstration de noix de totos est plus savante mais elle demande de connaitre la fonction de von Mangoldt et de savoir ce qu'est une identité de convolution.
j'ai corrigé ma bêtise.
Décidément, tu me confonds souvent et je t'en remercie beaucoup!
Amicalement
Paul
On suppose la formule vrai pour $n$ donné on veut la prouver pour $n+1$.
On prend les indices $i$ tel que $i$ divise $n+1$, $(i<n+1)$, c'est claire que $$\ppcm(1,2,\ldots, \text{E}(\frac{n}{i}))\neq \ppcm(1,2,\ldots,\text{E}(\frac{n+1}{i}))\Longleftrightarrow \dfrac{n+1}{i}=p_s^{\beta}$$ avec $1\le s \le k$ et $1\le \beta\le \alpha_s$ pour un certain entier $s$. Le reste doit être direct.
Cordialement.
en espérant, cette fois, ne pas dire de sottises.
Notations
$\forall n \in \mathbb {N^*},\ \forall i \in [[1,n]]$,
$P[n]:= \ppcm (1,2,\ldots,n)$
$P(n,i):=\ppcm(1,2,\ldots,E\big(\dfrac{n}{i})\big)$.
$$\prod_{i=1}^{n+1}\ppcm(1,2,\ldots,\text{E}(\frac{n+1}{i}))=\prod_{i\in A}\ppcm(1,2,\ldots,\text{E}(\frac{n+1}{i}))\times \prod_{i\in B}\ppcm(1,2,\ldots,\text{E}(\frac{n+1}{i}))=\prod_{i\in B}\ppcm(1,2,\ldots,\text{E}(\frac{n}{i}))\times \prod_{i\in A}\ppcm(1,2,\ldots,\text{E}(\frac{n}{i}))\times(\prod_{j=1}^kp_j^{\alpha_j})=n!(n+1)$$
La dernière égalité vient du fait que $\ppcm(1,2,\ldots, p_s^{\beta}-1,p_s^{\beta})=\ppcm(1,2,\ldots, p_s^{\beta}-1)\times p_s$ avec $ p_s^{\beta}-1=\text{E}(\frac{n}{i_0})$ pour un $i_0\in A.$
Bonjour
en espérant, cette fois, ne pas dire de sottises.
Notations
$\forall n \in \mathbb {N_{>1}},\ \forall i \in [[1,n]]$,
$P[n]:= \ppcm (1,2,\ldots,n)$
Proposition 1
$\forall m\in \mathbb {N_{>1}}$,
si $m$ est primaire $(:=p^r)$, alors $P[m]=pP[m-1]$, sinon $P[m]=P[m-1]$.
Autrement dit,
si $m$ est primaire $(:=p^r)$, alors $Q(m):=\dfrac{P[m]}{ P[m-1]} =p$, sinon $1$.
Proposition 2
$\forall n \in \mathbb {N_{>1}},\ \forall i \in [[1,n]]$,
si $\dfrac{n}{i}$ est primaire $(:=p^r)$ alors $Q(\lfloor \dfrac{n}{i} \rfloor)=p$, sinon $1$.
En effet,
si $\dfrac{n}{i}$ n'est pas entier, alors $\lfloor \dfrac{n}{i} \rfloor=\lfloor \dfrac{n-1}{i} \rfloor $, donc $P[ \lfloor \dfrac{n}{i} \rfloor ]=P[ \lfloor \dfrac{n-1}{i} \rfloor ]$, donc $Q(\lfloor \dfrac{n}{i} \rfloor)=1$;
si $\dfrac{n}{i}$ est entier, il découle de la proposition 1 que
si $\dfrac{n}{i}$ est primaire $(:=p^r)$, $Q(\lfloor \dfrac{n}{i} \rfloor)=Q( \dfrac{n}{i}) =p$ et
si $\dfrac{n}{i}$ n'est pas primaire, $Q(\lfloor \dfrac{n}{i} \rfloor)=Q( \dfrac{n}{i}) =1$
Conséquence
$\forall n \in \mathbb {N_{>1}}$,
dans la liste $L_n$ des $Q(\lfloor \dfrac{n}{i} \rfloor)$ où $i$ décrit $[[1,n]]$, le nombre d'occurrences de tout diviseur premier $p$ de $n$ est $v_p(n)$, si bien que le produit des éléments de $L_n$ n'est autre que $n$.
Il me semble que c'est fini.
Cordialement
Paul
Désolé de ne pas avoir répondu plus tôt. J'ai bien lu vos messages et finalement j'ai conclu par Legendre. Je vous remercie.