# Arithmétique/Nombres premiers
## 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é

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

## Lemme d'Euclide

Le lemme suivant est un corollaire immédiat du théorème de Gauss.
Pour tous entiers a et b, si un nombre premier p divise le produit ab, alors il divise a ou b.

## Décomposition en facteurs premiers

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.
(Par convention, $1$ est le produit vide.)
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$_1$ distinct de 1 et de n. Alors n = n$_1$ n$_2$, où n$_1$ et n$_2$ sont des nombres naturels non nuls, tous deux < n. Par hypothèse de récurrence, n$_1$ et n$_2$ 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.
La décomposition de $360$ est $360=2^{3}\times 3^{2}\times 5^{1}$.
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

Il existe une infinité de nombres premiers.
« 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

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.$
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)
| Théorèmes de Bézout et Gauss | PPCM |