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

Propriété des entiers naturels

Propriété

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

Par exemple : le plus petit entier strictement supérieur à $1$ divisant $n$.

Ensemble des nombres premiers

Dénombrement des 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 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.

 

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 et $a_{1},a_{2},...a_{k}$ des entiers naturels non nuls.

Fin du théorème

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

Démonstration

L'existence se déduit (par récurrence) de l'existence d'un diviseur premier (voir supra) et l'unicité, du lemme d'Euclide.

 

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

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$.