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 < 2 n

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 2 < p < (n + 1) 2$ . 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 $(2 n + 1) < (2 n) 2$ :

$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

Portail des mathématiques

Ce document provient de « Postulat de Bertrand ».

Catégories : Arithmétique modulaire | Théorie des nombres

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème de Tchebychev de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

Tchebychev — Pafnouti Tchebychev Pafnouti Tchebychev Pafnouti Lvovitch Tchebychev (en russe : Пафнутий Львович Чебышёв) (4 mai 1821 à Okatovo, près de Boro … Wikipédia en Français
Tchébychev — Pafnouti Tchebychev Pafnouti Tchebychev Pafnouti Lvovitch Tchebychev (en russe : Пафнутий Львович Чебышёв) (4 mai 1821 à Okatovo, près de Boro … Wikipédia en Français
Theoreme d'Abel (algebre) — Théorème d Abel (algèbre) Pour les articles homonymes, voir Théorème d Abel. Niels Henrik Abel (1802 … Wikipédia en Français
Théorème d'Abel-Ruffini — Théorème d Abel (algèbre) Pour les articles homonymes, voir Théorème d Abel. Niels Henrik Abel (1802 … Wikipédia en Français
Théorème d'Abel (Algèbre) — Pour les articles homonymes, voir Théorème d Abel. Niels Henrik Abel (1802 … Wikipédia en Français
Théorème d'abel (algèbre) — Pour les articles homonymes, voir Théorème d Abel. Niels Henrik Abel (1802 … Wikipédia en Français
Théorème de De Moivre — Formule de De Moivre Pour les articles homonymes, voir Moivre. Abraham de Moivre à qui est attribuée la formule La formule de De Moivre affi … Wikipédia en Français
Théorème de Donsker — simulations de Xn de n=100 à n=800 avec U de loi uniforme sur l ensemble { 1,1} En Théorie des probabilités, le Théorème de Donsker établie la convergence en loi d une marche aléatoire vers un Processus stochastique gaussien. Il est parfois… … Wikipédia en Français
Théorème d'Abel (algèbre) — Pour les articles homonymes, voir Théorème d Abel. Niels Henrik Abel (1802 1829) présente la première démonstration rigoureuse et co … Wikipédia en Français
Théorème des nombres premiers — En mathématiques, et plus précisément en théorie des nombres, le théorème des nombres premiers est un résultat concernant la distribution asymptotique des nombres premiers. Sommaire 1 Énoncé du théorème 2 Histoire 3 Ébauche de la preuve … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Théorème de Tchebychev

Postulat de Bertrand

Sommaire

Historique

Théorème de Sylvester