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

---

Vues : 42