Les nombres premiers

I. Définition

Un nombre est premier s’il possède exactement deux diviseurs qui sont 1 et lui-même

Exemples :

$\checkmark$ Les seuls diviseurs de $2$sont $1$ et $2$. Donc $2$ est un nombre premier.

$\checkmark$ Les seuls diviseurs de $7$sont $1$ et $7$. Donc $7$ est un nombre premier.

Attention : $1$ n'est divisible que par lui-même $1$, et ne comporte donc qu'un seul diviseur et non deux comme le réclame la définition. Le nombre $1$ n'est pas un nombre premier.

II. Une liste des nombres premiers inférieurs à $120$

Voici un algorithme qui procède par élimination afin de trouver les nombres premiers : il s'agit de supprimer d'une table des entiers de 2 à N tous les multiples d'un entier (autres que lui-même). En supprimant tous ces multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier à part 1 et eux-mêmes, et qui sont donc les nombres premiers.

Cette animation (issue de Wikipedia) est un extrait du crible d'Ératosthène$^*$ . Au final, ne seront pas éliminés les nombres premiers.

On trouve : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113

_{$^*$ Ératosthène ou Ératosthène de Cyrène né vers 276 av. J.-C. en Grèce, est un astronome, géographe, philosophe et mathématicien.}

III. Tester si un nombre est premier

Exemple 1 : le nombre $731$ est-il un nombre premier ?

Avec les critères de divisibilité connus, $731$ n'est ni divisible par $2$, par $3$, par $5$.

par $7$ : $731=104\times 7+3$ donc $731$ n'est pas divisible par $7$.

par $11$ : $731=66\times 11+5$ donc $731$ n'est pas divisible par $11$.

par $13$ : $731=56\times 13+3$ $731$ n'est pas divisible par $13$.

par $17$ : $731=43\times 17$

Conclusion : le nombre $731$ n'est pas un nombre premier.

Exemple 2 : le nombre $173$ est-il un nombre premier ?

Utilisons les critères de divisibilité que nous connaissons, et divisons par tous les entiers premiers successifs.

$173$ n'est pas divisible par $2$, ni par $3$, ni par $5$.

$173=24\times 7+5$ donc $173$ n'est pas divisible par $7$.

$173=15\times 11+8$ donc $173$ n'est pas divisible par $11$.

$173=13\times 13+4$ donc $173$ n'est pas divisible par $13$.

Faut-il continuer ? le nombre premier suivant serait $17$ à tester, mais celui-ci aurait déjà été trouvé en effectuant les divisions précédentes. Donc on peut s'arrêter, et on peut affirmer que le nombre $173$ est un nombre premier.

Pour aller plus loin : Test d'arrêt

Si le quotient devient inférieur au diviseur, on peut s'arrêter. En effet, si l'entier $N$ n'admet aucun diviseur parmi les nombres premiers successifs jusqu'à la valeur $\sqrt N$ , il n'en admettra pas non plus entre $\sqrt N$ et $N$ car les diviseurs d'un nombre vont par paires

Dit autrement, pour savoir si un nombre $N$ est premier, on peut s'arrêter si l'on doit dépasser $\sqrt N$ à tester.