Exercice 1 5930 Correction

Soient $a, b \in ℤ$ et $p$ un nombre premier. On suppose qu’il existe $α \in ℕ^{*}$ tel que $p^{α}$ divise le ppcm de $a$ et $b$ . Établir que $p^{α}$ divise $a$ ou $b$ .

Solution

Notons $v_{p} (n)$ la valuation $p$ -adique $n \in ℕ^{*}$ :

v_{p} (n) = \max {k \in ℕ | p^{k} ∣ n} .

On sait

v_{p} (a \lor b) = \max (v_{p} (a), v_{p} (b)) .

Si $p^{α}$ divise $a \lor b$ , alors $\max (v_{p} (a), v_{p} (b)) \geq α$ et donc $v_{p} (a) \geq α$ ou $v_{p} (b) \geq α$ . On en déduit que $p^{α}$ divise $a$ ou $b$ .

Exercice 2 1226 Correction

Pour $p \in 𝒫$ et $n \in ℤ$ , on note $v_{p} (n)$ l’exposant de la plus grande puissance de $p$ divisant $n$ .

(a)

Montrer que $v_{2} (1 000!) = 994$ .
(b)

Plus généralement, calculer $v_{p} (n!)$ . On rappelle que

$\forall x \in ℝ, ⌊ \frac{⌊ p x ⌋}{p} ⌋ = ⌊ x ⌋ .$

Solution

(a)

$v_{2} (1 000!) = 500 + v_{2} (500!)$ car $1000! = 2^{500} \times 500! \times k$ avec $k$ produit de nombres impairs.
$v_{2} (1 000!) = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 994$ .
(b)

En isolant les multiples de $p$ dans le produit décrivant $p!$ , on obtient

$v_{p} (n!) = ⌊ \frac{n}{p} ⌋ + v_{p} (⌊ \frac{n}{p} ⌋!)$

puis

$v_{p} (n!) = ⌊ \frac{n}{p} ⌋ + ⌊ \frac{⌊ n / p ⌋}{p} ⌋ + v_{p} (⌊ \frac{⌊ n / p ⌋}{p} ⌋!)$

or

$⌊ \frac{⌊ p x ⌋}{p} ⌋ = ⌊ x ⌋$

avec $x = n / p^{2}$ donne

$⌊ \frac{⌊ n / p ⌋}{p} ⌋ = ⌊ \frac{n}{p^{2}} ⌋$

puis finalement

$v_{p} (n!) = ⌊ \frac{n}{p} ⌋ + ⌊ \frac{n}{p^{2}} ⌋ + \dots + ⌊ \frac{n}{p^{k}} ⌋$

avec

$k = ⌊ \frac{\ln (n)}{\ln (p)} ⌋ .$

Exercice 3 4412

(Formule de Legendre)

(a)

Soient $p$ un nombre premier et $n \in ℕ$ . Établir

$v_{p} (n!) = \sum_{i = 1}^{r} ⌊ \frac{n}{p^{i}} ⌋ avec r = ⌊ \frac{\ln (n)}{\ln (p)} ⌋ .$
(b)

Application : Soient $a, b \in ℕ$ . Montrer

$\frac{(2 a)! (2 b)!}{a! b! (a + b)!} \in ℕ .$

Exercice 4 2370 CENTRALE (MP)Correction

On note $𝒫$ l’ensemble des nombres premiers. Pour tout entier $n > 0$ , on note $v_{p} (n)$ l’exposant de $p$ dans la décomposition de $n$ en facteurs premiers. On note $⌊ x ⌋$ la partie entière de $x$ . On note $π (x)$ le nombre de nombres premiers au plus égaux à $x$ .

(a)

Montrer

$v_{p} (n!) = \sum_{k = 1}^{+ \infty} ⌊ \frac{n}{p^{k}} ⌋ .$
(b)

Montrer que $(\binom{2 n}{n})$ divise $\prod_{p \in 𝒫; p \leq 2 n} p^{⌊ \frac{\ln (2 n)}{\ln (p)} ⌋}$ .
(c)

Montrer que $(\binom{2 n}{n}) \leq {(2 n)}^{π (2 n)}$ .
(d)

Montrer que $\frac{x}{\ln (x)} = O (π (x))$ quand $x \to + \infty$

Solution

(a)

Pour $k$ suffisamment grand $⌊ n / p^{k} ⌋ = 0$ , la somme évoquée existe donc car elle ne comporte qu’un nombre fini de termes non nuls. $n! = 1 \times 2 \times \dots \times n$ , parmi les entiers allant de 1 à $n$ , il y en a exactement $⌊ n / p ⌋$ divisibles par $p$ , $⌊ n / p^{2} ⌋$ divisibles par $p^{2}$ , etc…donc

$v_{p} (n!) = \sum_{k = 1}^{+ \infty} ⌊ \frac{n}{p^{k}} ⌋ .$
(b)

On a

$(\binom{2 n}{n}) = \frac{(2 n)!}{{(n!)}^{2}} .$

Pour tout $p \in 𝒫$ ,

$v_{p} (\frac{(2 n)!}{{(n!)}^{2}}) = \sum_{k = 1}^{\infty} (⌊ \frac{2 n}{p^{k}} ⌋ - 2 ⌊ \frac{n}{p^{k}} ⌋)$

or $⌊ 2 x ⌋ - 2 ⌊ x ⌋ = 0$ ou 1 donc

$\sum_{k = 1}^{\infty} (⌊ \frac{2 n}{p^{k}} ⌋ - 2 ⌊ \frac{n}{p^{k}} ⌋) \leq Card {k \in ℕ^{*} | ⌊ 2 n / p^{k} ⌋ > 0} \leq ⌊ \frac{\ln (2 n)}{\ln (p)} ⌋ .$

De plus, les nombres premiers diviseurs de $(\binom{2 n}{n}) = \frac{(2 n)!}{{(n!)}^{2}}$ sont diviseurs d’un entier inférieur à $2 n$ (lemme d’Euclide) et sont donc eux-mêmes inférieur à $2 n$ . Il en découle

$(\binom{2 n}{n}) ∣ \prod_{p \in 𝒫; p \leq 2 n} p^{⌊ \frac{\ln (2 n)}{\ln (p)} ⌋}$

car toutes les puissances de nombres premiers intervenant dans la décomposition de $(\binom{2 n}{n})$ divisent $\prod_{p \in 𝒫; p \leq 2 n} p^{⌊ \frac{\ln (2 n)}{\ln (p)} ⌋}$ .
Notons qu’en fait ce produit désigne

$ppcm (1,2, \dots,2 n) .$
(c)

On a

$(\binom{2 n}{n}) \leq \prod_{p \in 𝒫; p \leq 2 n} p^{⌊ \frac{\ln (2 n)}{\ln (p)} ⌋} \leq \prod_{p \in 𝒫; p \leq 2 n} p^{\frac{\ln (2 n)}{\ln (p)}} \leq \prod_{p \in 𝒫; p \leq 2 n} (2 n) = {(2 n)}^{π (2 n)} .$
(d)

En passant au logarithme:

$\sum_{k = 1}^{2 n} \ln (k) - 2 \sum_{k = 1}^{n} \ln (k) \leq π (2 n) \ln (2 n) .$

À l’aide d’une comparaison intégrale on obtient

$\int_{1}^{n} \ln (t) d t \leq \sum_{k = 1}^{n} \ln (k) \leq \int_{1}^{(n + 1)} \ln (t) d t$

donc

$n \ln (n) - n + 1 \leq \sum_{k = 1}^{n} \ln (k) \leq (n + 1) \ln (n + 1) - n$

donc

$\sum_{k = 1}^{n} \ln (k) \underset{n \to + \infty}{=} n \ln (n) - n + O (\ln (n)) .$

Par suite,

$\sum_{k = 1}^{2 n} \ln (k) - 2 \sum_{k = 1}^{n} \ln (k) \underset{n \to + \infty}{=} 2 n \ln (2 n) - 2 n - 2 (n \ln (n) - n) + O (\ln (n))$

puis

$\sum_{k = 1}^{2 n} \ln (k) - 2 \sum_{k = 1}^{n} \ln (k) \underset{n \to + \infty}{\sim} \ln (2) (2 n) .$

On en déduit

$\frac{2 n}{\ln (2 n)} \underset{n \to + \infty}{=} O (π (2 n)) .$

Ajoutons

$\frac{x}{\ln (x)} \underset{n \to + \infty}{\sim} \frac{2 ⌊ x / 2 ⌋}{\ln (2 ⌊ x / 2 ⌋)}$

par calculs et $π (x) \sim π (2 ⌊ x / 2 ⌋)$ car $π (x)$ et $π (2 ⌊ x / 2 ⌋)$ ne différent qu’au plus d’une unité et $π (x) \to + \infty$ .
Finalement, une certaine satisfaction.

Exercice 5 6155 CENTRALE (MP)Correction

Dans cet exercice, on note $𝒫$ (respectivement $𝒫_{n}$ ) l’ensemble des nombres premiers (respectivement, des nombres premiers inférieurs ou égaux à $n$ ).

Pour $p \in 𝒫$ et $n \in ℕ^{*}$ , on note $v_{p} (n)$ l’exposant de $p$ dans la décomposition de $n$ en facteurs premiers.

(a)

Écrire une fonction python premiers(n) renvoyant une liste de taille $n + 1$ telle que premier(n)[k] vaut $1$ si $k$ est premier et $0$ sinon.
(b)

Figurer les fonctions $n \mapsto \sum_{p \in 𝒫_{n}} \frac{\ln (p)}{p}$ , $n \mapsto \ln (n) - \ln (4) - 1$ et $n \mapsto \ln (n) + \ln (4)$ . Formuler une conjecture.
(c)

On fixe dans cette question un nombre premier $p$ et un entier $n ⩾ 1$ . Montrer que, pour tout $k \in ℕ$ ,

$Card {m \in ⟦ 1; n ⟧ | v_{p} (m) = k} = ⌊ \frac{n}{p^{k}} ⌋ - ⌊ \frac{n}{p^{k + 1}} ⌋ .$

En déduire que

$v_{p} (n!) = \sum_{k = 1}^{+ \infty} ⌊ \frac{n}{p^{k}} ⌋$

puis que

$\frac{n}{p} - 1 ⩽ v_{p} (n!) ⩽ \frac{n}{p - 1} .$
(d)

Proposer un encadrement de $\ln (n!)$ .
(e)

Montrer que pour tout entier $n ⩾ 2$ , il existe $θ_{n} \in [0; 1]$ tel que

$\ln (n!) = n \ln (n) - n + 1 + θ_{n} \ln (n) .$
(f)

Établir que $\prod_{p \in 𝒫_{n}} p ⩽ 4^{n}$ pour tout $n \in ℕ^{*}$ et conclure quant à la conjecture énoncée précédemment.

Solution

(a)

Par le crible d’Ératosthène,

def premiers(n):
    L = [0 for _ in range(n+1)]
    if n >= 2:
        L[2:] = [1]*(n-1)
    for p in range(2, int(n**0.5)+1):
        if L[p] == 1:
            for k in range(p*p, n+1, p):
                L[k] = 0
    return L

(b)

On obtient les tracés par le code suivant:

import matplotlib.pyplot as plt
N = 100
P = np.array(premiers(N))
n = np.array([1] + list(range(1, N+1)))
P = P * np.log(n)/n

plt.plot(n, np.log(n) - np.log(4) - 1)
plt.plot(n, np.cumsum(P))
plt.plot(n, np.log(n) + np.log(4))
plt.show()

Ces tracés suggèrent l’encadrement

\ln (n) - \ln (4) - 1 ⩽ \sum_{p \in 𝒫_{n}} \frac{\ln (p)}{p} ⩽ \ln (n) + \ln (4) .

(c)

Soit $k \in ℕ$ . Les entiers $m \in ⟦ 1; n ⟧$ tels que $v_{p} (m) = k$ sont ceux divisibles par $p^{k}$ mais pas par $p^{k + 1}$ . Pour $q \in ℕ^{*}$ donné, le nombre d’entiers $m \in ⟦ 1; n ⟧$ divisisible par $q$ est exactement $⌊ n / q ⌋$ et donc

$Card {m \in ⟦ 1; n ⟧ | v_{p} (m) = k} = ⌊ \frac{n}{p^{k}} ⌋ - ⌊ \frac{n}{p^{k + 1}} ⌋ .$

La propriété $v_{p} (m m^{'}) = v_{p} (m) + v_{p} (m^{'})$ pour $m, m^{'} \in ℕ^{*}$ donne

$v_{p} (n!) = \sum_{m = 1}^{n} v_{p} (m) .$

On réorganise le calcul de la somme selon de la valeur $k$ de $v_{p} (m)$

$v_{p} (n!) = \sum_{k = 1}^{+ \infty} \sum_{\binom{1 ⩽ m ⩽ n}{v_{p} (m) = k}} k = \sum_{k = 1}^{+ \infty} k (⌊ \frac{n}{p^{k}} ⌋ - ⌊ \frac{n}{p^{k + 1}} ⌋) .$

Les termes sommés sont nuls à partir d’un certain rang, on peut séparer la somme en deux et conclure à l’aide d’un glissement d’indice

$v_{p} (n!) = \sum_{k = 1}^{+ \infty} k ⌊ \frac{n}{p^{k}} ⌋ - \sum_{k = 1}^{+ \infty} k ⌊ \frac{n}{p^{k + 1}} ⌋ = \sum_{k = 1}^{+ \infty} k ⌊ \frac{n}{p^{k}} ⌋ - \sum_{k = 2}^{+ \infty} (k - 1) ⌊ \frac{n}{p^{k}} ⌋ = \sum_{k = 1}^{+ \infty} ⌊ \frac{n}{p^{k}} ⌋ .$

Sachant $x - 1 ⩽ ⌊ x ⌋ ⩽ x$ , on obtient l’encadrement

$\frac{n}{p} - 1 ⩽ ⌊ \frac{n}{p} ⌋ ⩽ \sum_{k = 1}^{+ \infty} ⌊ \frac{n}{p^{k}} ⌋ ⩽ \sum_{k = 1}^{+ \infty} \frac{n}{p^{k}} = \frac{n}{p - 1}$

donc

$\frac{n}{p} - 1 ⩽ v_{p} (n!) ⩽ \frac{n}{p - 1} .$
(d)

Puisque

$n! = \prod_{p \in 𝒫_{n}} p^{v_{p} (n!)}$

on a

$\ln (n!) = \sum_{p \in 𝒫_{n}} v_{p} (n!) \ln (p) .$

En utilisant les encadrements précédents

$\sum_{p \in 𝒫_{n}} (\frac{n}{p} - 1) \ln (p) ⩽ \ln (n!) ⩽ \sum_{p \in 𝒫_{n}} \frac{n}{p - 1} \ln (p) .$
(e)

La fonction $t \mapsto \ln (t)$ est continue par morceaux et croissante sur $[1; + \infty [$ . Par comparaison série-intégrale,

$\int_{1}^{n} \ln (t) d t ⩽ \sum_{k = 2}^{n} \ln (k) = \sum_{k = 1}^{n - 1} \ln (k) + \ln (n) ⩽ \int_{1}^{n} \ln (t) d t + \ln (n) .$

On en déduit

$n \ln (n) - n + 1 ⩽ \ln (n!) ⩽ n \ln (n) - n + 1 + \ln (n)$

puis l’existence $θ_{n} \in [0; 1]$ tel que

$\ln (n!) = n \ln (n) - n + 1 + θ_{n} \ln (n) .$
(f)

On établit $\prod_{p \in 𝒫_{n}} p ⩽ 4^{n}$ en raisonnant par récurrence forte sur $n \in ℕ^{*}$ .

Pour $n = 1$ et $n = 2$ , c’est immédiat.

Supposons la propriété vérifiée jusqu’au rang $n ⩾ 2$ .

Si $n + 1$ n’est pas un nombre premier, alors

$\prod_{p \in 𝒫_{n + 1}} p = \prod_{p \in 𝒫_{n}} p ⩽ 4^{n} .$

Si $n + 1$ est un nombre premier, nécessairement impair, on écrit $n + 1 = 2 m + 1$ .

Les nombres premiers compris entre $m + 2$ et $2 m + 1$ divisent tous $(\binom{2 m + 1}{m})$ et l’on a

$(\binom{2 m + 1}{m}) = \frac{1}{2} [(\binom{2 m + 1}{m}) + (\binom{2 m + 1}{m + 1})] ⩽ \frac{1}{2} {(1 + 1)}^{2 m + 1} = 4^{m} .$

Par l’hypothèse de récurrence,

$\prod_{p \in 𝒫_{n + 1}} p = \prod_{p \in 𝒫_{m + 1}} p \prod_{p \in 𝒫_{n + 1} ∖ 𝒫_{m + 1}} ⩽ 4^{m + 1} \cdot 4^{m} = 4^{n + 1} .$

La récurrence est établie.

L’inégalité

$\sum_{p \in 𝒫_{n}} (\frac{n}{p} - 1) \ln (p) ⩽ \ln (n!)$

donne

$\sum_{p \in 𝒫_{n}} \frac{\ln (p)}{p} ⩽ \frac{1}{n} \ln (n!) + \frac{1}{n} \sum_{p \in 𝒫_{n}} \ln (p) .$

D’une part,

$\frac{1}{n} \ln (n!) ⩽ \frac{1}{n} \ln (n^{n}) = \ln (n) .$

D’autre part,

$\sum_{p \in 𝒫_{n}} \ln (p) = \ln (\prod_{p \in 𝒫_{n}} p) ⩽ \ln (4^{n}) = n \ln (4) .$

On a donc

$\sum_{p \in 𝒫_{n}} \frac{\ln (p)}{p} ⩽ \ln (n) + \ln (4) .$

L’inégalité

$\ln (n!) ⩽ \sum_{p \in 𝒫_{n}} \frac{n \ln (p)}{p - 1}$

donne

$\sum_{p \in 𝒫_{n}} \frac{\ln (p)}{p} ⩾ \frac{1}{n} \ln (n!) - \sum_{p \in 𝒫_{n}} \frac{\ln (p)}{p (p - 1)} .$

D’une part,

$\frac{1}{n} \ln (n!) ⩾ \ln (n) - 1 + \frac{1}{n} ⩾ \ln (n) - 1 .$

D’autre part,

$\sum_{p \in 𝒫_{n}} \frac{\ln (p)}{p (p - 1)} ⩽ \sum_{p \in 𝒫_{n}} \ln (p) = \ln (\prod_{p \in 𝒫_{n}} p) ⩽ \ln (4^{n}) = n \ln (4) .$

On obtient donc

$\sum_{p \in 𝒫_{n}} \frac{\ln (p)}{p} ⩾ \ln (n) - \ln (4) - 1 .$

Exercice 6 5689 Correction

Soit $n \in ℕ^{*}$ . Si $n = \bar{ε_{p} ε_{p - 1} \dots ε_{0}}$ est l’espression de $n$ en base $2$ on note

s (n) = ε_{0} + \dots + ε_{p} et v (n) la valuation de n en base 2

(a)

Écrire une fonction calculant $v (n)$ et $s (n)$ .
(b)

Si $n \in {2, \dots {,10}^{4}}$ , vérifier numériquement que $v (n) = s (n - 1) - s (n) + 1$ .
(c)

Prouver que pour tout $n \geq 2$ , $v (n) = s (n - 1) - s (n) + 1$ .
(d)

Calculer $v (n!)$ en fonction de $n$ et $s (n)$ .
(e)

Soit $n \in ℕ^{*}$ . Montrer que $n$ est une puissance de $2$ si, et seulement si, $(\binom{n}{k})$ est un entier pair pour tout $k = 1, \dots, n - 1$ .

Solution

(a)

Tant qu’une puissance de $2$ divise $n$ , on passe à la puissance suivante:

def v(n):
    k = 0
    p = 1
    while n % (2*p) == 0:
        k = k + 1
        p = 2 * p
    return k

Pour calculer $s (n)$ , une solution récursive est possible:

def s(n):
    if n == 0:
        return 0
    elif n % 2 == 0:
        return s(n//2)
    else:
        return 1 + s((n-1) // 2)

(b)

On vérifie qu’aucune valeur n’échoue

for n in range(2, 10**4+1):
    if v(n) != s(n-1) - s(n) + 1:
        print(f"Echec pour la valeur {n}")

(c)

Posons $p$ la valuation de $n$ en base $2$ . L’écriture en base $2$ de $n$ se termine par $\bar{10 \dots 0}$ avec un nombre de zéro égal à $p$ . L’écriture de $n - 1$ commence par les mêmes chiffres mais se termine par $\bar{01 \dots 1}$ . On en déduit $s (n - 1) - s (n) = p - 1 = v (n) - 1$ .
(d)

Pour $p, q \in ℕ^{*}$ , $v (p q) = v (p) + v (q)$ donc

$v (n!) = \sum_{k = 1}^{n} v (k) = v (1) + \sum_{k = 2}^{n} (s (k - 1) - s (k) + 1) = n - s (n)$
(e)

Cas: $n = 1$ ou $n = 2$ . C’est immédiat.

Cas: $n \geq 3$ . Soit $k \in {1, \dots, n - 1}$ . On remarque

$v ((\binom{n}{k})) = v (n!) - v (k!) - v ((n - k)!) = s (k) + s (n - k) - s (n)$

Si $n$ vaut $2^{p}$ , son écriture en base de $2$ est de la forme $\bar{10 \dots 0}$ avec $p$ chiffres $0$ . Pour $k \in {1, \dots, n - 1}$ , les chiffres de l’écriture en base $2$ de $n - k$ sont les « inverses » des chiffres en base de $2$ de $k$ puisque $k + (n - k) = n$ . En particulier, $s (k) + s (n - k) = p$ . On a donc $s (k) + s (n - k) - s (n) = p - 1 > 0$ . Le coefficient binomial $(\binom{n}{k})$ est pair.

Si $n$ n’est pas une puissance de $2$ , on peut écrire avec $n = \bar{ε_{p} \dots ε_{q + 1} 10 \dots 0}$ . Considérons alors $k = 2^{q}$ . On a $s (k) = 1$ et $s (n - k) = ε_{p} + \dots + ε_{q + 1}$ donc $s (k) + s (n - k) = s (n)$ . Par conséquent, la valuation en base $2$ du coefficient binomial $(\binom{n}{k})$ est nulle: c’est entier est impair.

[<] Études arithmétiques [>] Petit théorème de Fermat

Édité le 06-05-2026

Valuation p-adique