Formule de Legendre

BMaths · March 2020

Bonjour,
j'ai un petit point de blocage pour démontrer la formule de Legendre.
Voici le cadre de l'exercice.- $n$ est un entier tel que $n\ge 2$ ;
- $p$ désigne un nombre premier ;
- $k_0\ge 1$ est le plus petit entier tel que $n<p^{k_0}$ ;
- On définit l'ensemble $\Omega_k:=\{a\in 1,n\mid v_p(a)=k\},$ où $v_p$ désigne la valuation $p$-adique.
J'ai démontré que $\ 1,n=\bigsqcup\limits_{k=0}^{k_0-1}\Omega_k$
Je viens d'écrire que $v_p(n!)=\sum\limits_{a\in 1,n }v_p(a)$.
Je cherche à comprendre pourquoi je peux écrire : $$
\sum_{a\in 1,n }v_p(a)=\sum_{k=0}^{k_0-1}\sum_{a\in\Omega_k}v_p(a)\quad ?

$$ Intuitivement, je sais que la réunion est disjointe est que donc $a\in 1,n\Longleftrightarrow \exists k\in 0,k_0-1,\ a\in\Omega_k$. Donc je comprends l'égalité, mais n'arrive pas à la formaliser.
Pouvez-vous m'aider ?
D'avance merci.

PS. Par la suite, j'arrive jusqu'à la conclusion sans souci, à savoir $v_p(n!)=\sum_{k\ge 0}k\times \mathrm{card}(\Omega_k)$.
Je bloque juste sur cette égalité.

noix de totos · March 2020

Pour moi, il n'y a rien à ajouter de plus : ton équivalence est suffisante pour expliquer le passage de la somme de gauche à celle de droite (tu sommes sur une partition de $\{1, \dotsc,n \}$, en quelque sorte).

Mais je dirais ceci : que cet exercice est bien compliqué pour montrer cette identité, qui se résume en fait à
$$v_p(n!) = \sum_{k=1}^n v_p(k) = \sum_{k=1}^n \sum_{h=1}^{v_p(k)} 1 = \sum_{h=1}^\infty \sum_{\substack{k=1 \\ v_p(k) \geqslant h}}^n 1 = \sum_{h=1}^\infty \left \lfloor \frac{n}{p^h} \right \rfloor$$
puisque la somme intérieure compte le nombre de multiples de $p^h$ inférieurs ou égaux à $n$. À noter que la somme sur $h$ est bien entendu finie.

BMaths · March 2020

Cela m'intrigue quand même. Le passage d'une seule somme, à deux. Sans autre forme de démonstration que l'équivalence -_-

J'avais essayé un changement de variable sur mon brouillon, mais sans succès.

Sinon, pour l'exercice, il existe certainement d'autres démonstrations, je veux bien vous croire

noix de totos · March 2020

BMaths a écrit:

Sinon, pour l'exercice, il existe certainement d'autres démonstrations, je veux bien vous croire

Oui : celle que j'ai donné est la plus connue et la plus rapide.

BMaths · March 2020

Je n'ai pas assez de connaissances, mais je vous fait confiance !
A vrai dire, c'est la première fois que j'entends parler de la formule de Legendre

Par contre, je reste un peu sur ma faim.

Je pensais vraiment qu'il existait un moyen de l'écrire qui rende concret l'apparition de la double somme.

OShine · March 2020

Il doit y avoir une explication pour la double somme.
Noix de Totos va un peu vite parfois, il faut avoir un niveau solide pour tout comprendre.

noix de totos · March 2020

O Shine a écrit:

Noix de Totos va un peu vite parfois.

Désolé si mes messages sont parfois un peu brefs.

Mais ici, selon moi, l'explication donnée par BMaths dit clairement pourquoi cette somme se "dédouble" :

(i) On somme au départ sur un certain ensemble d'entiers, ici $E = \{1, \dotsc,n \}$.

(ii) Cet ensemble est ensuite découpé en une partition.

CL. Ainsi, pour obtenir la somme complète sur $E$, on somme les sommes sur chaque partition.

OK ?

OShine · March 2020

Ah en effet c'est simple avec la partition vous avez raison, il n'y a pas de difficulté sur ce point.

BMaths · March 2020

Merci pour cette clarification.

noix de totos a écrit:

CL. Ainsi, pour obtenir la somme complète sur $E$, on somme les sommes sur chaque partition.

Je pense mieux saisir le fond.
Mais je bute encore sur la forme, c-à-d le passage d'une union à une somme.

Ce que je comprends, c'est que :
$\sum_{a\in 1,n }v_p(a)=\large\sum_{a\in\bigsqcup\limits_{k=0}^{k_0-1}\Omega_k}v_p(a)\quad$.

Mais pourquoi - comment ? - peut-on avoir :
$\large\sum_{a\in\bigsqcup\limits_{k=0}^{k_0-1}\Omega_k}v_p(a)\quad=\sum_{k=0}^{k_0-1}\sum_{a\in\Omega_k}v_p(a)\quad ?$

Peut-on l'expliquer "symboliquement" ? (ie. avec des symboles mathématiques)

noix de totos · March 2020

Je ne suis pas certain que, dans ce type d'exercice, il faille absolument déterminer une formule. Prenons un exemple : $n=20$, $p=2$, donc $k_0 = 5$ et $\Omega_0 = \{1,3,5,7,9,11,13,15,17,19\}$, $\Omega_1 = \{2,6,10,14,18\}$, $\Omega_2 = \{4,12,20\}$, $\Omega_3 = \{8\}$ et $\Omega_4 = \{16\}$.

On note bien la partition de $\{1,\dotsc,20\}$ par ces ensembles $\Omega_k$. Maintenant, au lieu de sommer "bêtement"
$$\sum_{a=1}^{20} v_2(a) = v_2(1) + \dotsb + v_2(20) = 18$$
on peut sommer par paquet en tenant compte de la partition
$$\sum_{a=1}^{20} v_2(a) = 0 \times 10 + 1 \times 5 + 2 \times 3 + 3 \times 1 + 4 \times 1 = 18.$$
Autrement dit, et sans explication supplémentaire, on a
$$\sum_{a=1}^{n} v_p(a) = \sum_{k=0}^{k_0-1} k \times \textrm{Card} \left( \Omega_k \right) = \sum_{k=0}^{k_0-1} k \sum_{a \in \Omega_k} 1 = \sum_{k=0}^{k_0-1} \sum_{a \in \Omega_k} k = \sum_{k=0}^{k_0-1} \sum_{a \in \Omega_k} v_p(a).$$

Remarque. Si tu veux toutefois une formule, c'est exactement le même phénomène que dans cette identité que tu connais bien
$$\textrm{Card} \left( \bigcup_{k=0}^N A_k \right) = \sum_{k=0}^N \textrm{Card}(A_k)$$
où $\left \{ A_0, \dotsc,A_N \right \}$ forme une partition d'un ensemble $E$ fini, égalité qui peut se réécrire sous la forme
$$\sum_{a \, \in \underset{k \in \{0, \dotsc,N\}}{\bigcup A_k}} 1 = \sum_{k=0}^N \sum_{a \in A_k} 1.$$

BMaths · March 2020

Je crois que je le "vois" un peu mieux.

Supposons que $A=\{1,2,3,4,5,6\}$.

Prenons comme partition $A_1=\{1,2,3\}$, $A_2=\{4,5\}$ et $A_3=\{6\}$.

Alors $a\in A$ signifie que $a\in A_1$ ou $a\in A_2$ ou $a\in A_3$.

D'une part $\sum_{a\in A}a=\sum_{a=1}^6a$.

D'autre part :
- $\sum_{a\in A_1}a=\sum_{a=1}^3a$
- $\sum_{a\in A_2}a=\sum_{a=4}^5a$
- $\sum_{a\in A_3}a=\sum_{a=6}^6a$.

En conséquence de quoi : $\sum_{a\in A_1}a+\sum_{a\in A_2}a+\sum_{a\in A_3}a=\sum_{a=1}^6a=\sum_{a\in A}a$.

Ce qui donne : $\sum_{i=1}^3\sum_{a\in A_i}a=\sum_{a\in A}a$.