Les nombres premiers

II. Théorème : reconnaître un nombre premier

Soit $n$ un entier naturel strictement supérieur à $1$.

Si $1$ est le seul diviseur de $n$ inférieur à $\sqrt{n}$, alors $n$ est un nombre premier.

Démonstration

Raisonnons par l’absurde : supposons que $n$ ne soit pas premier.
Alors il existerait deux entiers $m$ et $m'$ tels que $2 \leq m \leq m'$ et $m \times m' = n$.

En multipliant par $m$ cette inégalité, on obtiendrait $m^2 \leq m m'$, c’est-à-dire $m^2 \leq n$.

On en déduit qu’il existerait un entier $m \leq \sqrt{n}$ et différent de $1$ divisant $n$ : ceci est faux par hypothèse.

Un exemple : 43 est-il un nombre premier ?

$\sqrt{43} \approx 6.5$.

Or $43$ n’est pas divisible par :

$\checkmark$ $2$ puisqu’il ne se termine pas par $0$, $2$, $4$, $6$ ou $8$.

Donc $43$ est premier.

Conséquence

Un nombre n > 1 est premier si et seulement si il n’admet aucun diviseur premier inférieur ou égal à $\sqrt{n}$.

III. Théorème de décomposition d'un nombre premier

Tout entier naturel $n \geq 2$ s’écrit de façon unique sous la forme d’un produit

$p_1^{a_1} \times p_2^{a_2} \times ... \times p_n^{a_n}$ où $p_1, p_2, ..., p_n$ sont des nombres premiers distincts et les $a_i$ sont des entiers naturels non nuls.

Remarque

Ce théorème permet donc de dire que tout nombre entier supérieur ou égal à $2$ est divisible par au moins un nombre premier.

Théorème

Il existe une infinité de nombres premiers.

Démonstration (au programme)

Pour montrer que l’ensemble des nombres premiers est infini, il suffit de montrer que, quel que soit le nombre $n \geq 2$, il existe un nombre premier plus grand que $n$.

Considérons le nombre $m = n! + 1$.

$\circ$ Si $m$ est premier, alors comme m > n, il existe un nombre premier plus grand que $n$.

$\circ$ Si $m$ n’est pas premier, alors il admet au moins un diviseur premier $p$. Mais $m$ n’est divisible par aucun nombre $k$ avec $2 \leq k \leq n$. En effet, $n!$ est multiple de $k$, mais $1$ ne l’est pas, donc $n! + 1$ n’est pas multiple de $k$. Par conséquent, p > n.

Dans tous les cas, il existe donc un nombre premier plus grand que $n$.

Il existe cependant une méthode générale pour décomposer un nombre en facteurs premiers.

Pour la mettre en œuvre, il est préférable de connaître le début de la liste des nombres premiers, ceux inférieurs à $50$.

Examinons cette méthode sur un exemple :

IV. Point méthode

Énoncé

Décomposons $6636$ en un produit de facteurs premiers.

Comme $\sqrt{79} \approx 8.8$, on constate que $79$ ne possède aucun diviseur premier inférieur à $\sqrt{79}$.
Donc $79$ est un nombre premier.

Conclusion : $6636 = 2 \times 2 \times 3 \times 7 \times 79$.

Disposition pratique et principe de décomposition en facteurs premiers