Nombres premiers


1. Nombres premiers. Nombres composés

Définition 1.
Un nombre entier naturel $p$, supérieur ou égal à $2$ est dit premier lorsqu’il n’admet pas d’autres diviseurs positifs que $1$ et lui-même.
Autrement dit :
Un nombre entier naturel $p$, supérieur ou égal à $2$ est dit premier lorsqu’il admet exactement deux diviseurs positifs, $1$ et lui-même.

Cette définition exclut le nombre $1$ ; donc $1$ n’est pas un nombre premier car $1$ admet exactement un seul diviseur : $1$ qui n’est autre que lui-même.

Définition 2.
Un nombre entier naturel $n$, distinct de $1$, qui n’est pas premier est dit composé.

Exemples

$2$ ; $3$ ; $5$ ; $7$ ; $11$ sont des nombres premiers. $6$ ; $9$ ; $12$ sont un nombre composé.

2. Propriétés des nombres premiers

2. Comment déterminer si un entier est premier ?

2.1. Un algorithme

1°) Une première technique consiste à utiliser un algorithme ou un programme sur calculatrice.
Pour chaque entier $N$ saisi, on crée une boucle qui teste la divisibilité de $N$ par tous les entiers non nuls qui le précèdent.

Pour cela il suffit que « pour (tous les entiers) $k$ allant de $1$ à $N$ », de calculer $N/k$, et de vérifier si le quotient $N/k$ est entier, c’est-à-dire « si $N/k = E(N/k)$ » où $E$ désigne la partie entière d’un nombre réel. Cette fonction existe sur toutes les calculatrices programmables ! A vous de jouer.

2.2. Une technique ancestrale : Le crible d’Ératosthène

2°) Nous connaissons une méthode, vielle de plusieurs siècles, appelée méthode des cribles. Pour déterminer tous les nombres premiers compris entre $1$ et un entier naturel $N$ quelconque, donné.

Le crible d’Ératosthène [Mathématicien grec 284-192 avant J.C.]

Cette méthode permet de déterminer la liste de tous les nombres premiers inférieurs à un nombre entier donné $N$. Cette méthode se base sur la propriété suivante fondamentale suivante :

Propriété 1.
Pour tout entier naturel $p$, tous les multiples de $p$, qui sont strictement supérieurs à $p$, ne sont pas premiers.

Démonstration.

Soit $p$ un entier naturel et $n$ un multiple strict de $p$.
Par définition, il existe un entier $k$ tel que $n=kp$, avec $k>1$. Alors $n$ admet au moins 4 diviseurs qui sont : $1$, $k$, $p$ et $n$. Donc $n$ n’est pas premier. CQFD.

Exemple

Exercice résolu n°1.
Utiliser le crible d’Ératosthène pour déterminer tous les nombres premiers compris entre $1$ et $100$.

On construit un tableau carré comportant $10$ colonnes de $1$ à $10$ dans lequel on note tous les entiers compris entre $1$ et $N$.

  • On barre le $1$ qui n’est pas premier.
  • On conserve le $2$ et on raye tous ses multiples stricts dans l’ordre croissant à partir de $2^2$.
  • On conserve le $3$ et on raye tous ses multiples stricts dans l’ordre croissant à partir de $3^2$.
  • On conserve le $5$ et on raye tous ses multiples stricts dans l’ordre croissant à partir de $5^2$.
  • Et ainsi de suite. On conserve chaque premier nombre $k$ rencontré et on raye tous ses multiples stricts dans l’ordre croissant à partir de $k^2$.
  • On continue tant que $k^2<N$, c’est-à-dire pour tout $k<\sqrt{N}$.
  • Les nombres entiers non rayés sont donc tous les entiers premiers inférieurs ou égaux à $N$.

On construit un tableau carré comportant $10$ colonnes de $1$ à $10$ dans lequel on note tous les entiers compris entre $1$ et $100$.
On cherche le point d’équilibre : $\sqrt{100}=10$. Les nombres premiers inférieurs à $10$ sont : $2$ ; $3$ ; $5$ ; $7$.

Fig. 1. Crible Érathostène. Nombres premiers inférieurs à $100$.
  • On barre le $1$ qui n’est pas premier.
  • On conserve le $2$ et on raye tous les nombres pairs à partir de $2^2$.
  • On conserve le $3$ et on raye tous ses multiples de $3$ à partir de $3^2$.
  • On conserve le $5$ et on raye tous ses multiples de $5$ à partir de $5^2$.
  • On conserve le $7$ et on raye tous ses multiples de $7$ à partir de $7^2$.
  • $11^2>100$. On s’arrête.
  • Les nombres entiers non rayés sont donc tous les entiers premiers inférieurs ou égaux à $100$.

Conclusion. La liste des nombres premiers inférieurs à $100$ est :
$2$ ; $3$ ; $5$ ; $7$ ; $11$ ; $13$ ; $17$ ; $19$ ; $23$ ; $29$ ; $31$ ; $37$ ; $41$ ; $43$ ; $47$ ; $53$ ; $59$ ; $61$ ; $67$ ; $71$ ; $73$ ; $79$ ; $83$ ; $89$ et $97$.