mathématiques MPSI · Chapitre 7 · Exercice de TD

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

Arithmétique dans l'ensemble des entiers relatifs · G. Décomposition en facteurs premiers, PGCD et PPCM par les valuations · niveau 2

Énoncé

Pour $p$ premier et $n \in N^{*}$ , $v_{p} (n)$ désigne la valuation $p$ -adique de $n$ .

a) Soient $a, b \in N^{*}$ . Montrer que $v_{p} (a \land b) = min (v_{p} (a), v_{p} (b))$ et $v_{p} (a \lor b) = max (v_{p} (a), v_{p} (b))$ , et en déduire $(a \land b) (a \lor b) = ab$ .

b) Formule de Legendre. Montrer que $v_{p} (n!) = k \geq 1 \sum ⌊ \frac{n}{p ^{k}} ⌋$ (somme finie).

c) Par combien de zéros se termine l'écriture décimale de $100!$ ?

d) Montrer que $v_{2} (n!) = n - s_{2} (n)$ , où $s_{2} (n)$ est la somme des chiffres de $n$ en base $2$ . En déduire que $n!$ n'est jamais divisible par $2^{n}$ .

Corrigé de la question 1

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 ∣ b$ si et seulement si $v_{p} (a) \leq 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^{m i n (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) \leq v_{p} (a)$ et $v_{p} (c) \leq v_{p} (b)$ , donc $v_{p} (c) \leq 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 \land b) = min (v_{p} (a), v_{p} (b))$ .

Le même raisonnement, les inégalités renversées, montre que $m = \prod_{p} p^{m a x (v_{p} (a), v_{p} (b))}$ est un multiple commun qui divise tout multiple commun : $v_{p} (a \lor 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 \land b) (a \lor 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 \land b) (a \lor b) = ab$ .

Question 2 : comment l'IA t'aide

b) Formule de Legendre. Montrer que $v_{p} (n!) = k \geq 1 \sum ⌊ \frac{n}{p ^{k}} ⌋$ (somme finie).

Élève

J'écris $v_{p} (n!) = \sum_{m = 1}^{n} v_{p} (m)$ . Je vois que $⌊ n / p ⌋$ compte les multiples de $p$ , mais les multiples de $p^{2}$ apportent plus d'un facteur $p$ , et je ne sais pas comment organiser le décompte.

Commence par $v_{p} (m)$ pour un seul entier $m$ : peux-tu l'écrire comme le nombre d'entiers $k \geq 1$ vérifiant une certaine propriété liée à $p^{k}$ ?

Élève

$p^{k}$ divise $m$ si et seulement si $k \leq v_{p} (m)$ , donc $v_{p} (m)$ est le nombre de $k \geq 1$ tels que $p^{k} ∣ m$ . Alors $v_{p} (n!)$ devient une somme double de $1$ .

Quels couples $(m, k)$ cette somme double compte-t-elle ? Si tu les comptes dans l'autre ordre, $k$ fixé d'abord, que dénombres-tu, et pourquoi n'y a-t-il qu'un nombre fini de $k$ qui contribuent ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →