Théorème de Tchebychev

Postulat de Bertrand

En mathématiques, le postulat de Bertrand, aussi appelé théorème de Tchebychev, affirme qu'entre un entier et son double existe toujours un nombre premier. Plus formellement, si n est un entier naturel supérieur ou égal à 2, alors il existe toujours au moins un nombre premier p tel que

n < p < 2n

Bien que démontré, il a gardé son nom de postulat, c'est-à-dire une conjecture.

Historique

Cette affirmation fut pour la première fois conjecturée en 1845 par Joseph Bertrand qui la vérifia lui-même pour tous les nombres de l'intervalle $[2 ; 3 \times 10^6]$. La conjecture fut complètement démontrée en 1850 par Pafnouti Tchebychev, qui utilisa dans sa démonstration la formule de Stirling.

Ramanujan donna une démonstration plus simple et Paul Erdős en 1932 publia une preuve très simple dans laquelle il utilisa les coefficients binomiaux et la fonction θ, définie par:

$\theta(x) = \sum_{p=2}^{x} \ln (p)$

où p parcourt les nombres premiers inférieurs ou égaux à x.

Théorème de Sylvester

Le postulat de Bertrand fut avancé en vue d'applications au groupe des permutations. James Joseph Sylvester le généralisa avec la proposition suivante : le produit de k entiers consécutifs supérieurs à k est divisible par un nombre premier plus grand que k.

Une conjecture similaire, appelée conjecture de Legendre, mais non encore résolue affirme l'existence, pour tout entier naturel non nul n, d'un nombre premier p tel que n² < p < (n + 1)². Elle touche à l'hypothèse de Riemann.

Démonstration

Nous noterons l'ensemble des nombres premiers $\Bbb{P}$ et définissons :

$\theta(x) = \sum_{p\in\Bbb{P};\, p\leq x} \ln (p)$

Voici le plan de la démonstration:

• Majoration de θ(x)
• Vérification explicite de la propriété pour n ≤ 2048
• Démonstration de la propriété pour n > 2048
• Conclusion.

Lemme

pour tous les entiers $n\ge 1$:

$\theta(n) < n \cdot \ln(4)$

Démonstration

• n = 1:

$\theta(1)= 0 < 1 \cdot \ln(4)$

• n = 2:

$\theta(2)=\ln(2) < 2 \cdot \ln(4)$

• n > 2 et n est pair :

$\theta(n) = \theta(n-1) < (n-1) \cdot \ln(4) < n \cdot \ln(4)$ (par induction)

(parce que chaque nombre pair n'est pas premier, donc il y a autant de nombres premiers entre 1 et n qu'avec 1 et n-1 )

• n > 2 et n est impair. Soit n = 2m+1 avec m > 0:

$4^m = \frac {(1+1)^{2m+1}}{2} = \frac {\sum_{k=0}^{2m+1}{2m+1 \choose k}} {2} = \frac {x+{2m+1 \choose m}+{2m+1 \choose m+1}}{2} \ge {2m+1 \choose m}$

Chaque nombre premier p avec $m+1 < p \le 2m+1$ divise ${2m+1 \choose m}$ ce qui nous donne :

$\theta(2m+1) - \theta(m+1) \le \ln({2m+1 \choose m}) \le \ln(4^m) = m \cdot \ln(4)$

Par induction $\theta(m+1) < (m+1) \cdot \ln 4$, donc :

$\theta(n) = \theta(2m+1) < (2m+1) \cdot \ln(4) = n \cdot \ln(4)$

CQFD

Maintenant, pour la démonstration du postulat de Bertrand.

Supposons qu'il existe un contre-exemple : un entier n ≥ 2 tel qu'il n'existe pas de nombre premier p avec n < p < 2n.

Cas où n ≤ 2048

Si 2 ≤ n ≤ 2048, considérons la suite de nombres premiers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 et 2503, chacun étant strictement inférieur au double de son prédécesseur. Puisque n est supposé ≤ 2048, n est strictement inférieur à au moins un nombre premier de cette liste (à savoir le plus grand, 2503). Nous pouvons donc considérer le plus petit nombre premier de cette liste, soit p, tel que

(1) n < p.

Si p = 3, alors n = 2 et le théorème est vrai (puisque 2 < 3 < 4). Nous pouvons donc supposer que p est strictement supérieur à 3. Alors p a un prédécesseur dans la liste, soit q. Par minimalité de p, nous avons

(2) q ≤ n.

Par construction de la liste des nombres premiers ci-dessus,

(3) p < 2q,

En multipliant les deux membres de (2) par 2, nous trouvons 2q ≤ 2n, donc (3) donne

p < 2n.

Joint à (1), ceci donne n < p < 2n. Le théorème est donc vrai si 2 ≤ n ≤ 2048 et nous sommes ramenés au cas où n > 2048.

Cas où n > 2048

Par la formule du binôme de Newton,

$4^n=(1+1)^{2n}=\sum_{k=0}^{2n}{2n \choose k}$

Puisque ${2n \choose n}$ est le plus grand terme de la somme, nous avons :

$\frac {4^n} {2n+1} \le {2n \choose n}$

Appelons R(p,n) le plus grand nombre x tel que p^x divise ${2n \choose n}$.

Puisque n! possède $\sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor$ facteurs de p nous obtenons :

$R(p,n)=\sum_{j=1}^\infty \left \lfloor \frac {2n} {p^j} \right \rfloor-2\sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor=\sum_{j=1}^\infty \left \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor$

Puisque chaque terme $\left \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor$ vaut soit 0 (lorsque $\left \{\frac {n} {p^j}\right \} < \frac{1}{2}$) soit 1 (lorsque $\left\{\frac {n} {p^j} \right\} \ge \frac{1}{2}$) et que tous les termes avec $j> \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$ sont nuls, nous obtenons :

$R(p,n) \le \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$

Pour $p > \sqrt{2n}$ nous avons $\left \lfloor \frac {\ln (2n)} {\ln(p)} \right \rfloor \le 1$ où $R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor$.

${2n \choose n}$ n'a pas de facteur premier p tel que :

• 2n < p, car 2n est le facteur le plus grand;
• $n<p \le 2n$, à cause d'un développement trivial de l'assertion originale (hypothèse que nous cherchons à contredire);
• $\frac {2n} {3} <p \le n$, car $p > \sqrt{2n}$ (puisque $n \ge 5$) qui nous donne $R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor = 2-2 = 0$.

Aucun facteur premier de ${2n \choose n}$ n'est donc plus grand que $\frac {2n} {3}$.

${2n \choose n}$ possède au plus un facteur de chaque nombre premier $p > \sqrt{2n}$. Comme $p^{R(p,n)} \le 2n$, le produit de p^R(p,n) pour tous les autres nombres premiers est au plus $(2n)^{\sqrt{2n}}$. Puisque ${2n \choose n}$ est le produit de p^R(p,n) pour tous les nombres premiers p, nous obtenons :

$\frac {4^n}{2n+1} \le {2n \choose n} \le (2n)^{\sqrt{2n}} \prod_{p \in \mathbb{P} }^{\frac {2n} {3}} p = (2n)^{\sqrt{2n}} e^{\theta(\frac {2n} {3})}$

En utilisant notre lemme $\theta(n) < n \cdot \ln(4)$:

$\frac {4^n} {2n+1} \le (2n)^{\sqrt{2n}} 4^{\frac {2n} {3}}$

Puisque nous avons (2n + 1) < (2n)²:

$4^{\frac {n}{3}} \le (2n)^{2+\sqrt{2n}}$

Et aussi $2 \le \frac {\sqrt{2n}}{3}$ (puisque $n \ge 18$):

$4^{\frac {n}{3}} \le (2n)^{\frac {4} {3}\sqrt{2n}}$

En prenant les logarithmes :

$\sqrt{2n} \ln(2) \le 4 \cdot \ln(2n)$

En substituant 2^2t pour 2n:

$\frac {2^t} {t} \le 8$

Ceci nous donne t < 6 et la contradiction :

$n=\frac {2^{2t}} {2}<\frac {2^{2 \cdot 6}} {2}=2048$

Conclusion

Ainsi, aucun contre-exemple pour le postulat n'est possible.

CQFD

Ce document provient de « Postulat de Bertrand ».