Cours : Nombre Premier
Introduction :
Il existe des nombres entiers naturels "difficiles à partager" comme : 2 ; 3 ; 5 ; 7 ; 11.
Ces nombres ont et n'ont que deux diviseurs positifs. On appelle de tels nombres des "nombres premiers".
Pour voir la liste des "premiers" entiers naturels premiers (ceci)
Les entiers naturels premiers ont aussi ceci de particulier :
ils permettent de décomposer les entiers naturels supérieurs ou égaux à 2 non premiers en produits de facteurs premiers.
C'est à dire :
Tout entier naturel supérieur ou égal à 2 et non premier se décompose d'une manière unique (à l'ordre des facteurs près) en un produit de nombres premiers (admis)
Par exemple :
\(36=2×18=2×2×9=2×2×3×3=2^2×3^2\)
\(2^2×3^2\) est la décomposition en produits de facteurs premiers de 36
Visualisation de la décomposition en produit de facteurs premiers (ceci)
Définition : Définition (Nombre premier)
Quel que soit le nombre entier naturel \(a \in \mathbb N.\)
"\(a\) est un nombre premier "
équivaut à
\(a \neq 1\) et l'ensemble des diviseurs de \(a\) est \(\{1,a\}\)
Exemple :
\(2\) est un nombre entier naturel premier car il admet exactement deux diviseurs (positifs) qui sont \(1\) et \(2\)
\(3\) est un nombre premier car il admet exactement deux diviseurs (positifs) qui sont \(\)1 et \(3\)
\(5\) est un nombre premier car il admet exactement deux diviseurs (positifs) qui sont \(1\) et \(5\)
Exemple : contre-exemple
\(0\) n'est pas premier car il admet une infinité de diviseurs
L'ensemble des diviseurs de \(0\) est \(\mathbb N\)
\(1\) n'est pas un nombre premier car il n'admet qu'un seul diviseur (positifs) qui est \(1\)
L'ensemble des diviseurs de \(0\) est \({1}\)
\(9\) n'est pas un nombre premier car il n'admet pas exactement deux diviseurs (positifs).
il admet \(1; 3; 9\) comme diviseurs (positifs)
L'ensemble des diviseurs de \(9\) est \({1 ;3 ;9}\)
Remarque :
La définition de la primalité d'un nombre entier naturelle donnée ci-dessus équivaut à chacune des propositions suivantes :
Quel que soit le nombre entier naturel \(a \in \mathbb N.\)
"\(a\) est un nombre premier "
équivaut à
\(a\) admet exactement deux diviseurs (positifs) qui sont \(1\) et \(a\) lui même.
Quel que soit le nombre entier naturel \(a \in \mathbb N.\)
"\(a\) est un nombre premier "
équivaut à
\(a \neq 1\) et Quel que soit \(b \in \mathbb N\), Si \(b\) divise \(a\) Alors \(b = 1\) ou \(b = a\)
Remarque : (admis)
L'ensemble des 10 premiers entiers naturels premiers est : \({2;3;5;7;11;13;17;19;23;29}\)
Il n'y a qu'un seul entier naturel premier et pair, c'est \(2\)
Tous les entiers naturels premiers mis à part \(2\) sont impairs
L'ensemble des nombres premiers est infini.
Attention : Propriété : (Décomposition d'un entier naturel en produit de nombres premiers)
Quel que soit l'entier naturel \(n\)
Si \(n\) est supérieur ou égal à \(2\)
Alors \(n\) est premier ou \(n\) est égal à un produit de facteurs premiers
(Un tel produit s'appelle "une décomposition en facteur premier de \(n\)")
Exemple :
\(4 = 2 \times 2 = 2^2\)
\(6 = 2 \times 3\)
\(12 = 2\times 2 \times 3 = 2^2 \times 3\)
On a la disposition pratique suivante :
Remarque :
Les nombres premiers permettent ainsi de reconstituer l'ensemble des entiers naturels sauf \(0\) et \(1\), par multiplication ou "par identité".
(un entier naturel non égal à \(0\) ou \(1\) est premier ou le produit de nombres premiers)
Attention : Propriété : ( test de primalité)
Quel que soit l'entier naturel \(n\),
Si \(n \geq 2\)
Alors
\(n\) est premier si et seulement si \(n\) n'admet aucun diviseur compris entre \(2\) inclus et \(\sqrt{n}\) inclus
Exemple :
\(\sqrt{17}\simeq 4,12\)
\(2,3\) et \(4\) ne sont pas des diviseurs de \(17\)
donc \(17\) est premier.
Remarque :
Pour montrer qu'un entier naturel \(n \geq 2\) est premier, il suffit de montrer qu'aucun entier compris entre \(2\) inclus et à \(\sqrt{n}\) inclus ne divise \(n\)
Il est possible d'automatiser la réponse à la question :"\(a\) est-il un nombre premier " ? (où \(a\) est un entier naturel connu). Pour cela, on écrit un algorithme correspondant au problème puis, on traduit l'algorithme dans un langage de programmation ( Le langage Python est au programme du Lycée) puis, on fait exécuter le programme par un ordinateur.
Voici un algorithme qui permet de déterminer si un entier naturel \(a \geq 2\) est un nombre premier en utilisant une boucle "tant que".
Simulation :
x ← a
i ← 2
Tant que x%i \(\neq 0\)
i← i+1
Fin Tant que
si i = x alors écrire "a est un nombre premier"
sinon écrire "a n'est pas un nombre premier"
Remarque :
Tant que x%i != 0
i← i+1
Fin Tant que
Les trois lignes ci-dessus constituent une "boucle" qui est exécutée tant que le reste de la division Euclidienne de x par i n'est pas égal à 0. Cette boucle teste si chacun des entiers i de 2 à x est un diviseur de x.
Comme x%x =0, la boucle s'arrête si un entier inférieur ou égal à x est un diviseur de x.
À la sortie de la boucle, si i est égal à x alors "x est premier" sinon"x n'est pas premier".
Voici un programme écrit dans le langage Python, qui permet de déterminer si un entier naturel \(a \geq 2\) est un nombre premier en utilisant une boucle "tant que"
Simulation :
x = int(input("Entrez la valeur de a supérieure ou égale à 2 S.V.P."))
i = 2
while x%i != 0 :
\(~~\) i = i+1
if i ==x :
\(~~\) print (x,"est premier")
else :
\(~~\) print (x,"n'est pas premier")
Remarque :
while x%i != 0 :
i = i+1
Les lignes ci-dessus constituent la "boucle" qui est exécutée tant que le reste de la division Euclidienne de x par i n'est pas égal à 0.
"n'est pas égal" s'écrit : " != " en Python
Exemple :
Lancez le programme qui se trouve (ici) en cliquant sur Run.
Puis entrer la valeur \(11\) pour \(a\)
puis observez ce qu'écrit le programme puis recommencez avec d'autres valeurs de \(a\)