Les valuations font tout : PGCD, PPCM et la formule de Legendre

Ce qu'on a le droit d'utiliser. L'unicité de la décomposition en facteurs premiers, et ses deux conséquences du cours : $v_p(ab)=v_p(a)+v_p(b)$, et $a\mid b$ si et seulement si $v_p(a)\le v_p(b)$ pour tout premier $p$. La stratégie : traduire la divisibilité en inégalités d'exposants, premier par premier — la valuation change l'arithmétique en comparaison d'entiers.

a) PGCD et PPCM. Posons $d={\prod }_p{p}^{\min (v_p(a),v_p(b))}$ (produit fini, car presque toutes les valuations sont nulles). Pour tout $p$, $v_p(d)=\min (v_p(a),v_p(b))$ est inférieur à $v_p(a)$ et à $v_p(b)$ : $d$ divise $a$ et $b$. Si $c$ est un autre diviseur commun, alors pour tout $p$, $v_p(c)\le v_p(a)$ et $v_p(c)\le v_p(b)$, donc $v_p(c)\le \min =v_p(d)$ : $c$ divise $d$. Ainsi tout diviseur commun divise $d$, et $d$ est un diviseur commun : $d$ est le plus grand diviseur commun (au sens de la divisibilité, donc aussi au sens de l'ordre), et $v_p(a\wedge b)=\min (v_p(a),v_p(b))$.

Le même raisonnement, les inégalités renversées, montre que $m={\prod }_p{p}^{\max (v_p(a),v_p(b))}$ est un multiple commun qui divise tout multiple commun : $v_p(a\vee b)=\max (v_p(a),v_p(b))$.

Enfin, pour deux entiers $u,v$, on a $\min (u,v)+\max (u,v)=u+v$. Donc pour tout $p$, $$v_p((a\wedge b)(a\vee b))=\min +\max =v_p(a)+v_p(b)=v_p(ab).$$ Deux entiers strictement positifs ayant les mêmes valuations pour tout premier sont égaux (unicité de la décomposition) : $(a\wedge b)(a\vee b)=ab$.

b) La formule de Legendre. La valuation d'un produit est la somme des valuations : $$v_p(n!)=\sum _{m=1}^n{v}_p(m).$$ Comptons autrement. Pour un entier $m\ge 1$, $v_p(m)$ est le nombre d'entiers $k\ge 1$ tels que $p^k$ divise $m$ (car $p^k\mid m$ si et seulement si $k\le v_p(m)$). Donc $$v_p(n!)=\sum _{m=1}^n\#\{k\ge 1:p^k\mid m\}=\sum _{k\ge 1}\#\{m\in \{1,\dots ,n\}:p^k\mid m\},$$ en échangeant les deux comptages — on compte les couples $(m,k)$ avec $1\le m\le n$, $k\ge 1$ et $p^k\mid m$, d'abord par $m$ puis par $k$. Les multiples de $p^k$ dans $\{1,\dots ,n\}$ sont $p^k,2p^k,\dots$, jusqu'au plus grand multiple inférieur à $n$, au nombre de $\lfloor \frac{n}{p^k}\rfloor$. D'où $$v_p(n!)=\sum _{k\ge 1}\lfloor \frac{n}{p^k}\rfloor .$$ Le point délicat. La somme est finie : dès que $p^k>n$, $\lfloor \frac{n}{p^k}\rfloor =0$. Sans cette remarque, le symbole n'aurait pas de sens. L'échange des deux sommations — compter une même chose de deux façons — est le geste central.

c) Les zéros de $100!$. Un zéro final est un facteur $10=2\times 5$ ; le nombre de zéros est $\min (v_2(100!),v_5(100!))$. Par Legendre : $$v_5(100!)=\lfloor \frac{100}{5}\rfloor +\lfloor \frac{100}{25}\rfloor =20+4=24,v_2(100!)=50+25+12+6+3+1=97.$$ $100!$ se termine par exactement $24$ zéros. Les facteurs $5$ sont beaucoup plus rares que les facteurs $2$ : c'est toujours la valuation en $5$ qui compte les zéros.

d) La valuation en $2$ et l'écriture binaire. Écrivons $n$ en base $2$ : $n={\sum }_{i=0}^m{b}_i{2}^i$ avec $b_i\in \{0,1\}$, et $s_2(n)=\sum b_i$. Pour $k\ge 1$, $$\frac{n}{2^k}=\sum _{i\ge k}{b}_i{2}^{i-k}+\sum _{i<k}{b}_i{2}^{i-k},$$ où la première somme est un entier et la seconde est comprise entre $0$ et ${\sum }_{i=0}^{k-1}{2}^{i-k}=1-2^{-k}<1$. Donc $\lfloor \frac{n}{2^k}\rfloor ={\sum }_{i\ge k}{b}_i{2}^{i-k}$. Par Legendre, en sommant sur $k$ puis en regroupant par $i$ : $$v_2(n!)=\sum _{k\ge 1}\sum _{i\ge k}{b}_i{2}^{i-k}=\sum _{i\ge 1}{b}_i\sum _{k=1}^i{2}^{i-k}=\sum _{i\ge 1}{b}_i\left(2^i-1\right)=\sum _i{b}_i{2}^i-\sum _i{b}_i=n-s_2(n),$$ car ${\sum }_{k=1}^i{2}^{i-k}=2^{i-1}+\cdots +2+1=2^i-1$ (et le terme $i=0$ contribue $b_0(2^0-1)=0$, ce qui permet d'inclure $i=0$ dans les deux dernières sommes). $v_2(n!)=n-s_2(n)$. Vérification : $100=64+32+4$ s'écrit $1100100$ en base $2$, $s_2(100)=3$, et $100-3=97$, conforme au c).

Comme $s_2(n)\ge 1$ pour $n\ge 1$ (l'écriture binaire d'un entier non nul a au moins un chiffre $1$), $v_2(n!)\le n-1<n$ : $2^n$ ne divise jamais $n!$.

Ce que l'exercice installe. Une fois les décompositions connues, PGCD et PPCM deviennent des min et des max coordonnée par coordonnée, et la relation $(a\wedge b)(a\vee b)=ab$ tombe d'une identité sur deux entiers. La formule de Legendre, elle, est un double comptage — le même que celui du chapitre de dénombrement — et sa version binaire relie l'arithmétique des factorielles à l'écriture des entiers, ce qui gouverne la parité des coefficients binomiaux. Réserve importante : décomposer est coûteux ; pour calculer un PGCD, Euclide reste incomparablement plus rapide.