Lycée > Seconde > Mathématiques > Les nombres premiers

Les nombres premiers

Fiche de cours Quiz Profs en ligne Vidéos Télécharger le pdf

Fiche de cours Quiz Profs en ligne Vidéos Télécharger
le pdf

Objectifs

Connaitre la définition d’un nombre premier.
Résoudre des problèmes mobilisant cette notion.
Déterminer à l’aide d’un algorithme si un entier naturel non nul est premier.

Points clés

On appelle nombre premier tout entier naturel qui n'admet que deux diviseurs distincts positifs : lui-même et 1.
La liste des entiers premiers positifs débute par :
2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 ; 23 ; 29 ; 31…
Soit un entier naturel. Si aucun entier premier inférieur ou égal à autre que 1 ne divise , alors est un entier premier.

Pour bien comprendre

Nombres entiers naturels et relatifs
Multiples et diviseurs
Algorithmique

1. Définition

On appelle nombre premier tout entier naturel qui n'admet que deux diviseurs distincts positifs : lui-même et 1.

Remarque
Les nombres 0 et 1 ne sont pas des nombres premiers.
En effet, 0 a une infinité de diviseurs et 1 n’a que lui-même pour diviseur positif.

Exemples
2, 3, 5, 11, 31 sont des nombres premiers.
21 admet quatre diviseurs positifs (1, 3, 7 et 21) donc ce n'est pas un nombre premier.

Propriété
La liste des nombres premiers débute par :
2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 ; 23 ; 29 ; 31…

2. Test de primalité

Un test qui détermine si un nombre entier est premier est appelé « test de primalité ».

Propriété
Soit

un entier naturel. Si aucun entier premier inférieur ou égal à

autre que 1 ne divise

, alors

est un entier premier.

Méthode

Pour tester si un entier est premier :

calculer sa racine carrée ;
tester si est divisible par tous les entiers naturels premiers compris entre 2 et .
Si un de ces entiers divise , alors c’est un diviseur de autre que 1 et , donc n’est pas premier. Sinon, est premier ;
conclure.

Exemple 1

est-il premier ?
On calcule

.
La liste des entiers premiers positifs inférieurs à 11 est {2 ; 3 ; 5 ; 7 ; 11}. On teste la divisibilité de 139 par ces nombres.

139 n’est pas divisible par 2 ni par 5.
3 × 46 = 138 donc 139 n’est pas divisible par 3.
7 × 20 = 140 donc 139 n’est pas divisible par 7.
Enfin, 11 × 12 = 132 et 11 × 13 = 143 donc 139 n’est pas divisible par 11.

Par conséquent, 139 est premier.

Exemple 2

est-il premier ?
On calcule

.
La liste des entiers premiers positifs inférieurs à 8 est {2 ; 3 ; 5 ; 7}. On teste la divisibilité de 69 par ces nombres.

69 n’est pas divisible par 2.
Mais 3 × 23 = 69, donc 69 est divisible par 3.

Par conséquent, 69 n’est pas premier.

3. Programmation

On peut déterminer à l’aide d’un programme si un entier naturel non nul est premier ou non.

Pour cela, on teste s’il est divisible par un des entiers inférieurs ou égaux à 29. Ainsi, on peut appliquer l’algorithme à tout entier inférieur ou égal à 29²= 841.

Ce programme affiche 1 si l’entier n est premier et 0 sinon.

Langage naturel	Langage Python
L=[2,3,5,7,11,13,17,19,23,29] Saisir n test ←1 k ← 0 Tant que test=1 et que k<=9 K ← l’entier L[k] Si K divise n alors test ← 0 k ← k+1 Fin Si Fin Tant que Afficher test	L1 L=[2,3,5,7,11,13,17,19,23,29] L2 n=input('n ?') L3 n=int(n) L4 test=1 L5 k=0 L6 while test==1 and k<=9: L7 K=int(L[k]) L8 if n%K==0: L9 test=0 L10 k=k+1 L11 print(test)

Quelques précision sur les instructions

L1 : on définit la liste qui contient les nombres premiers inférieurs ou égaux à 29.
L3 : l’instruction int permet de transformer le type d’une variable en entier. En effet, pour déterminer le reste d’une division entre deux entiers, il faut deux variables numériques de type entier.
L6 : la condition de la boucle while est vraie tant qu’on n’a pas trouvé de diviseur à n (test==1) et qu’on n’a pas passé en revue les entiers de la liste L (K<=9) pour savoir s’ils divisent n.
L8 : l’instruction n%K donne le reste de la division euclidienne de n par K. Si ce reste est égal à 0, alors n est divisible par K et n’est pas un entier.