Nombres premiers et test de primalité : Cours de Mathématiques 1BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ
Nombres premiers et test de primalité : notion du chapitre Arithmétique dans ℤ du programme de maths 1BAC SM, expliquée pas à pas, avec 3 exemples guidés. Pour les élèves de 1BAC Sciences Mathématiques, option française (BIOF).
Notions du cours (13)
Apprendre avec Burhan
Nombres premiers et test de primalité
Étape 1 sur 4Les nombres premiers
Devine : Un nombre premier ?

Les nombres premiers sont les briques des entiers : on les reconnaît, puis on casse chaque entier en briques. Commençons par les reconnaître.
Petit rappel. Au tronc commun, un nombre premier est un entier naturel qui a exactement deux diviseurs positifs. Lequel de ces nombres est premier ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :
Juste.
Juste : n'a que deux diviseurs positifs, et .
Choix B :
Faux.
n'a qu'un seul diviseur positif : il n'est pas premier.
Choix C :
Faux.
: il est impair, mais composé.
Choix D :
Faux.
: il est impair, mais composé.
Voir la correction complète
n'a qu'un diviseur positif. et ont d'autres diviseurs que et eux-mêmes. Quant à , il n'est divisible ni par , ni par , ni par , ni par , et . Tu verras plus loin pourquoi ces essais suffisent : est premier.
DéfinitionNombre premier
Un entier naturel est premier si et si ses seuls diviseurs positifs sont et . On note l'ensemble des nombres premiers.
Un entier naturel qui n'est pas premier est dit composé : il admet un diviseur positif autre que et , et alors .

Exemplepremiers et plus petit diviseur
Les nombres premiers inférieurs à sont , , , , , , , , et . Seul est pair.
Les diviseurs de supérieurs ou égaux à sont , et ; le plus petit, , est premier. Pourquoi est-ce vrai ? Si ce plus petit diviseur avait un diviseur tel que , alors diviserait aussi . Ce serait un diviseur plus petit que .

Étape 2 sur 4Le plus petit diviseur
PropriétéPlus petit diviseur d'un entier
Soit un entier naturel tel que . Le plus petit diviseur de tel que est un nombre premier. En particulier, tout entier naturel admet au moins un diviseur premier.
Démonstration
Étape 1. Les diviseurs de supérieurs ou égaux à forment une partie non vide de , car elle contient . Elle admet un plus petit élément (propriété de , admise).
Étape 2. Supposons par l'absurde que n'est pas premier. Comme , il admet un diviseur tel que (définition d'un nombre premier). Or et , donc (propriétés de la divisibilité). Ainsi est un diviseur de , avec et : cela contredit le choix de .
Étape 3. Donc est premier, et c'est un diviseur premier de .

À retenirRetenir de la preuve : le plus petit diviseur
On choisit le plus petit diviseur supérieur ou égal à , puis on raisonne par l'absurde : s'il n'était pas premier, il en existerait un plus petit. Ce schéma, « un plus petit élément, puis une contradiction », reviendra pour la décomposition.

Vérifie : Le plus petit diviseur

Quel est le plus petit diviseur de supérieur ou égal à ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :
Faux.
: ne divise pas .
Choix B :
Juste.
Juste : , et aucun entier de à ne divise .
Choix C :
Faux.
divise , mais il existe un diviseur plus petit.
Choix D :, car il est premier.
Faux.
: il n'est pas premier.
Voir la correction complète
On essaie les nombres premiers dans l'ordre : , , , . Enfin, . Le plus petit diviseur cherché est , et il est bien premier.
Exemplechercher un diviseur premier
Prenons . Aucun des nombres , , , , ne divise . Puis : le plus petit diviseur supérieur ou égal à est , premier, et . Pour , il n'y a aucun diviseur supérieur ou égal à : l'hypothèse est nécessaire.
Pourquoi est-ce vrai ? Si est composé, écrivons , avec son plus petit diviseur supérieur ou égal à . Le cofacteur divise aussi , et car ; donc , d'où .

Étape 3 sur 4Le test de primalité
PropriétéTest de primalité
Soit un entier naturel tel que . Si n'est pas premier, alors admet un diviseur premier tel que .
Par contraposée : si aucun nombre premier tel que ne divise , alors est premier.
Démonstration
Étape 1. Supposons composé. Notons le plus petit diviseur de supérieur ou égal à : est premier (plus petit diviseur). Il existe un entier naturel tel que .
Étape 2. Comme n'est pas premier, , donc ; et car . Ainsi . Or divise ; par le choix de , on a .
Étape 3. Donc . La seconde phrase de l'énoncé est la contraposée de la première.

À retenirRetenir de la preuve : le cofacteur
Dans , avec le plus petit diviseur, on a , donc . Conséquence pratique : pour prouver que est premier, il suffit de tester les nombres premiers tels que .

Vérifie : Le cofacteur

Dans l'étape 2 de la preuve, pourquoi a-t-on ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :Car est premier, alors que ne l'est pas forcément.
Faux.
Être premier ne compare pas à .
Choix B :Car est lui aussi premier, et plus grand que .
Faux.
Rien ne le dit : pour , et .
Choix C :Car divise , et est le plus petit tel diviseur.
Juste.
Juste : c'est le choix de qui fait tout.
Choix D :Car on sait déjà que .
Faux.
C'est la conclusion, pas l'argument.
Voir la correction complète
divise et ; par le choix de , plus petit diviseur de supérieur ou égal à , on a , donc .
Étape 4 sur 4Tester un entier
Méthodereconnaître un nombre premier
- Liste, pour un entier , les nombres premiers tels que :
- Teste la divisibilité de par chacun, dans l'ordre.
- Si l'un d'eux divise , alors est composé : comme , le diviseur vérifie .
- Si aucun ne divise , alors est premier, d'après le test de primalité.

ExempleExemple guidé : 323 et 331
Pour . On a . Aucun des nombres , , , , , ne divise . Puis : est composé.
Pour . On a . On teste , , , , , et : les restes sont , , , , , et . Aucun n'est nul : est premier.

À toi : Premier ou composé ?

Décide si et sont premiers, en justifiant chaque essai. Écris ta réponse avant de dévoiler la correction.
Besoin d'aide ? Indice 1
Pour chaque nombre, cherche le plus grand entier dont le carré ne le dépasse pas.
Encore bloqué ? Indice 2
et : les nombres premiers à tester sont au plus égaux à .
Encore bloqué ? Indice 3
Point délicat : un seul diviseur trouvé suffit pour conclure « composé » ; pour « premier », il faut tous les essais.
Voir la solution complète
On a . On teste , , , , et .
Pour : ni , ni , ni , ni , ni ne divise , mais . Donc est composé.
Pour : les restes par , , , , et sont , , , , et . Aucun n'est nul : est premier.
Attention1 n'est pas premier, et impair ne veut pas dire premier
✗ « est impair et ne finit pas par , donc il est premier. »
✓ est composé. Être impair élimine seulement le diviseur . Seul le test des nombres premiers tels que permet de conclure. Et n'est pas premier : il n'a qu'un diviseur positif.

← Étape précédenteFin de la notion
S'entraîner sur cette notion
Sources du cours
- Référentiel BURHAN du chapitre « Arithmétique dans ℤ » (1bac · sciences-mathematiques · mathematiques)
