Arithmétique/Nombres premiers

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Définition

Définition

Un entier naturel $n$ est premier s'il possède exactement 2 diviseurs naturels distincts, 1 et $n$.

ou

Un nombre est premier s'il est différent de 1 et divisible uniquement par 1 et par lui-même.

Les dix premiers nombres premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29.

Critère de primalité

Proposition

Si un entier naturel $n$ n'est divisible par aucun nombre premier dont le carré est inférieur ou égal à $n$, alors $n$ est premier.

Application : tant que $q<{\sqrt {n}}$, on tente la division de $n$ par $q$. 

Début de l'exemple

Exemple d’utilisation du critère de primalité

127 est-il premier ? $11\leq {\sqrt {127}}\leq 12$

Les nombres premiers inférieurs ou égaux à 11 sont : $2,3,5,7,11$

$127=2\times 63+1$

$127=3\times 42+1$

$127=5\times 25+2$

$127=7\times 18+1$

$127=11\times 11+6$

127 n'étant divisible par aucun nombre premier inférieur ou égal à 11, on en déduit qu'il est premier.

Fin de l'exemple

Lemme d'Euclide

Le lemme suivant est un corollaire immédiat du théorème de Gauss.

Début d'un lemme

Lemme d'Euclide

Pour tous entiers a et b, si un nombre premier p divise le produit ab, alors il divise a ou b.

Fin du lemme

Décomposition en facteurs premiers

Début d’un théorème

Théorème

Tout entier $n\geq 1$ peut se décomposer en un produit de nombres premiers. Cette décomposition est unique à l’ordre des facteurs près.

On l'écrit $n=p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{k}^{a_{k}}$, où $p_{1},p_{2},...p_{k}$ sont des nombres premiers distincts et $a_{1},a_{2},\dots ,a_{k}$ des entiers naturels non nuls.

Fin du théorème

(Par convention, $1$ est le produit vide.)

Démonstration

Soit n un nombre naturel non nul. Prouvons par récurrence sur n que n est décomposable en produit de facteurs premiers. Si n est égal à 1, il est le produit de la famille vide et l'énoncé est vrai. Si n > 1, ou bien n est premier et l'énoncé est vrai, ou bien n admet un diviseur naturel n₁ distinct de 1 et de n. Alors n = n₁ n₂, où n₁ et n₂ sont des nombres naturels non nuls, tous deux < n. Par hypothèse de récurrence, n₁ et n₂ sont tous deux décomposables en produits de facteurs premiers, donc n l'est aussi.

Nous avons donc prouvé que tout nombre naturel non nul est le produit d'une famille finie de nombres premiers. Prouvons que cette famille est unique à l’ordre près. Ici encore, nous raisonnons par récurrence sur n. Soient

$n=p_{1}\dots p_{r}$

et

$n=q_{1}\dots q_{s}$

deux décompositions de n en produit de facteurs premiers. Si r = 0, alors n = 1, donc les familles $p_{1},\dots ,p_{r}$ et $q_{1},\dots ,q_{s}$ sont toutes deux vides et la thèse est vraie. Nous pouvons donc supposer $r\geq 1$. D'après le lemme d'Euclide, $p_{r}$ divise un des nombres $q_{1},\dots ,q_{s}$, soit $q_{j}$. Puisque $q_{j}$ est premier, il est clair qu’il est égal à $p_{r}$. Donc $n/p_{r}$ admet les décompositions

$n/p_{r}=p_{1}\dots p_{r-1}$

et

$n/p_{r}=n/q_{j}=q_{1}\dots q_{j-1}q_{j+1}\dots q_{s}$.

Par hypothèse de récurrence sur n, les familles $p_{1},\dots ,p_{r-1}$ et $q_{1},\dots ,q_{j-1},q_{j+1},\dots ,q_{s}$ sont égales à l’ordre près, donc il en est de même des familles $p_{1},\dots ,p_{r}$ et $q_{1},\dots ,q_{s}$, ce qui achève la démonstration.

 

Début de l'exemple

Exemple

La décomposition de $360$ est $360=2^{3}\times 3^{2}\times 5^{1}$.

Fin de l'exemple

Corollaire

Tout entier $n$ strictement supérieur à $1$ admet au moins un diviseur premier.

On peut choisir par exemple le plus petit facteur premier dans la décomposition de $n$ ou remarquer, plus directement que le plus petit entier strictement supérieur à $1$ divisant $n$ est premier.

Application au calcul de PGCD

Une alternative à l'algorithme d'Euclide pour calculer le PGCD de deux entiers $a,b\geq 1$ est, si l'on connait leurs décompositions respectives, de former le produit de tous les nombres premiers $p$ intervenant dans ces deux décompositions, élevé chacun à une certaine puissance : l'exposant de $p$ dans $\operatorname {pgcd} \left(a,b\right)$ est le plus petit des deux exposants de $p$ dans $a$ et dans $b$.

Ensemble des nombres premiers

Infinitude de l'ensemble nombres premiers

Début d’un théorème

Théorème

Il existe une infinité de nombres premiers.

Fin du théorème

Démonstration

« Il existe une infinité de… » signifie : pour tout entier $n$, il en existe au moins $n$. Contrairement à ce qui est souvent affirmé, ce n'est pas une démonstration par l'absurde mais par récurrence. L'initialisation est immédiate et pour l'hérédité, on procède comme suit.

Soient $n$ nombres premiers distincts : $p_{1},p_{2},p_{3},\dots ,p_{n}$ et soit $N$ leur produit. Alors, $N+1$ est strictement supérieur à $1$ donc (voir supra) il possède au moins un facteur premier $p$.

Ce nombre premier $p$ est différent de $p_{1},p_{2},p_{3},\dots ,p_{n}$ car chaque $p_{j}$, divisant $N$ et ne divisant pas $1$, ne peut diviser $N+1$.

 

Théorème des nombres premiers

Début d’un théorème

Théorème

Le nombre π(x) de nombres premiers inférieurs ou égaux à x est équivalent, lorsque le réel x tend vers +∞, au quotient de x par son logarithme népérien. Soit : $\pi (x)\sim {\frac {x}{\ln(x)}}\ (x\to +\infty )$, c'est-à-dire : $\lim _{x\to +\infty }\pi (x){\frac {\ln(x)}{x}}=1.$

Fin du théorème

Note historique

Après avoir été conjecturé dans la marge d'une table de logarithmes par Gauss en 1792 ou 1793 alors qu'il avait seulement 15 ou 16 ans, le théorème a finalement été démontré indépendamment par Hadamard et La Vallée Poussin en 1896 à l'aide de méthodes d'analyse complexe, utilisant en particulier la fonction ζ (zêta) de Riemann.

 

Lien externe

https://oeis.org/A000040 : liste des premiers nombres premiers et leurs propriétés (en anglais)