BURHAN.

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 4

Les 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 :5353

Juste.

Juste : 5353 n'a que deux diviseurs positifs, 11 et 5353.

Choix B :11

Faux.

11 n'a qu'un seul diviseur positif : il n'est pas premier.

Choix C :5151

Faux.

51=3×1751 = 3 \times 17 : il est impair, mais composé.

Choix D :5757

Faux.

57=3×1957 = 3 \times 19 : il est impair, mais composé.

Voir la correction complète

11 n'a qu'un diviseur positif. 51=3×1751 = 3 \times 17 et 57=3×1957 = 3 \times 19 ont d'autres diviseurs que 11 et eux-mêmes. Quant à 5353, il n'est divisible ni par 22, ni par 33, ni par 55, ni par 77, et 8×8=64>538 \times 8 = 64 > 53. Tu verras plus loin pourquoi ces essais suffisent : 5353 est premier.

DéfinitionNombre premier

Un entier naturel pp est premier si p≥2p \geq 2 et si ses seuls diviseurs positifs sont 11 et pp. On note P\mathbb{P} l'ensemble des nombres premiers.

Un entier naturel n≥2n \geq 2 qui n'est pas premier est dit composé : il admet un diviseur positif dd autre que 11 et nn, et alors 1<d<n1 < d < n.

Exemplepremiers et plus petit diviseur

Les nombres premiers inférieurs à 3030 sont 22, 33, 55, 77, 1111, 1313, 1717, 1919, 2323 et 2929. Seul 22 est pair.

Les diviseurs de 9191 supérieurs ou égaux à 22 sont 77, 1313 et 9191 ; le plus petit, 77, est premier. Pourquoi est-ce vrai ? Si ce plus petit diviseur dd avait un diviseur ee tel que 1<e<d1 < e < d, alors ee diviserait aussi 9191. Ce serait un diviseur plus petit que dd.

Continuer : Le plus petit diviseur →

Étape 2 sur 4

Le plus petit diviseur

PropriétéPlus petit diviseur d'un entier

Soit nn un entier naturel tel que n≥2n \geq 2. Le plus petit diviseur dd de nn tel que d≥2d \geq 2 est un nombre premier. En particulier, tout entier naturel n≥2n \geq 2 admet au moins un diviseur premier.

Démonstration

Étape 1. Les diviseurs de nn supérieurs ou égaux à 22 forment une partie non vide de N\mathbb{N}, car elle contient nn. Elle admet un plus petit élément dd (propriété de N\mathbb{N}, admise).

Étape 2. Supposons par l'absurde que dd n'est pas premier. Comme d≥2d \geq 2, il admet un diviseur ee tel que 1<e<d1 < e < d (définition d'un nombre premier). Or e∣de \mid d et d∣nd \mid n, donc e∣ne \mid n (propriétés de la divisibilité). Ainsi ee est un diviseur de nn, avec e≥2e \geq 2 et e<de < d : cela contredit le choix de dd.

Étape 3. Donc dd est premier, et c'est un diviseur premier de nn.

À retenirRetenir de la preuve : le plus petit diviseur

On choisit le plus petit diviseur supérieur ou égal à 22, 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 143143 supérieur ou égal à 22 ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :77

Faux.

143=7×20+3143 = 7 \times 20 + 3 : 77 ne divise pas 143143.

Choix B :1111

Juste.

Juste : 143=11×13143 = 11 \times 13, et aucun entier de 22 à 1010 ne divise 143143.

Choix C :1313

Faux.

1313 divise 143143, mais il existe un diviseur plus petit.

Choix D :143143, car il est premier.

Faux.

143=11×13143 = 11 \times 13 : il n'est pas premier.

Voir la correction complète

On essaie les nombres premiers dans l'ordre : 143=2×71+1143 = 2 \times 71 + 1, 143=3×47+2143 = 3 \times 47 + 2, 143=5×28+3143 = 5 \times 28 + 3, 143=7×20+3143 = 7 \times 20 + 3. Enfin, 143=11×13143 = 11 \times 13. Le plus petit diviseur cherché est 1111, et il est bien premier.

Exemplechercher un diviseur premier

Prenons n=221n = 221. Aucun des nombres 22, 33, 55, 77, 1111 ne divise 221221. Puis 221=13×17221 = 13 \times 17 : le plus petit diviseur supérieur ou égal à 22 est 1313, premier, et 132=169≤22113^{2} = 169 \leq 221. Pour n=1n = 1, il n'y a aucun diviseur supérieur ou égal à 22 : l'hypothèse n≥2n \geq 2 est nécessaire.

Pourquoi est-ce vrai ? Si nn est composé, écrivons n=pmn = pm, avec pp son plus petit diviseur supérieur ou égal à 22. Le cofacteur mm divise aussi nn, et m≥2m \geq 2 car p≠np \neq n ; donc m≥pm \geq p, d'où p2≤pm=np^{2} \leq pm = n.

← Étape précédenteContinuer : Le test de primalité →

Étape 3 sur 4

Le test de primalité

PropriétéTest de primalité

Soit nn un entier naturel tel que n≥2n \geq 2. Si nn n'est pas premier, alors nn admet un diviseur premier pp tel que p2≤np^{2} \leq n.

Par contraposée : si aucun nombre premier pp tel que p2≤np^{2} \leq n ne divise nn, alors nn est premier.

Démonstration

Étape 1. Supposons nn composé. Notons pp le plus petit diviseur de nn supérieur ou égal à 22 : pp est premier (plus petit diviseur). Il existe un entier naturel mm tel que n=pmn = pm.

Étape 2. Comme nn n'est pas premier, p≠np \neq n, donc m≠1m \neq 1 ; et m≠0m \neq 0 car n≠0n \neq 0. Ainsi m≥2m \geq 2. Or mm divise nn ; par le choix de pp, on a p≤mp \leq m.

Étape 3. Donc p2≤pm=np^{2} \leq pm = n. La seconde phrase de l'énoncé est la contraposée de la première.

À retenirRetenir de la preuve : le cofacteur

Dans n=pmn = pm, avec pp le plus petit diviseur, on a p≤mp \leq m, donc p2≤np^{2} \leq n. Conséquence pratique : pour prouver que nn est premier, il suffit de tester les nombres premiers pp tels que p2≤np^{2} \leq n.

Vérifie : Le cofacteur

Dans l'étape 2 de la preuve, pourquoi a-t-on p≤mp \leq m ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Car pp est premier, alors que mm ne l'est pas forcément.

Faux.

Être premier ne compare pas pp à mm.

Choix B :Car mm est lui aussi premier, et plus grand que pp.

Faux.

Rien ne le dit : pour n=12n = 12, p=2p = 2 et m=6m = 6.

Choix C :Car m≥2m \geq 2 divise nn, et pp est le plus petit tel diviseur.

Juste.

Juste : c'est le choix de pp qui fait tout.

Choix D :Car on sait déjà que p2≤np^{2} \leq n.

Faux.

C'est la conclusion, pas l'argument.

Voir la correction complète

mm divise nn et m≥2m \geq 2 ; par le choix de pp, plus petit diviseur de nn supérieur ou égal à 22, on a p≤mp \leq m, donc p2≤pm=np^{2} \leq pm = n.

← Étape précédenteContinuer : Tester un entier →

Étape 4 sur 4

Tester un entier

Méthodereconnaître un nombre premier

  1. Liste, pour un entier n≥2n \geq 2, les nombres premiers pp tels que p2≤np^{2} \leq n : 2,3,5,7,…2, 3, 5, 7, \dots
  2. Teste la divisibilité de nn par chacun, dans l'ordre.
  3. Si l'un d'eux divise nn, alors nn est composé : comme p2≤np^{2} \leq n, le diviseur pp vérifie 1<p<n1 < p < n.
  4. Si aucun ne divise nn, alors nn est premier, d'après le test de primalité.

ExempleExemple guidé : 323 et 331

Pour 323323. On a 172=289≤323<324=18217^{2} = 289 \leq 323 < 324 = 18^{2}. Aucun des nombres 22, 33, 55, 77, 1111, 1313 ne divise 323323. Puis 323=17×19323 = 17 \times 19 : 323323 est composé.

Pour 331331. On a 182=324≤331<361=19218^{2} = 324 \leq 331 < 361 = 19^{2}. On teste 22, 33, 55, 77, 1111, 1313 et 1717 : les restes sont 11, 11, 11, 22, 11, 66 et 88. Aucun n'est nul : 331331 est premier.

À toi : Premier ou composé ?

Décide si 247247 et 251251 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

152=22515^{2} = 225 et 162=25616^{2} = 256 : les nombres premiers à tester sont au plus égaux à 1313.

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 152=225≤247<251<256=16215^{2} = 225 \leq 247 < 251 < 256 = 16^{2}. On teste 22, 33, 55, 77, 1111 et 1313.

Pour 247247 : ni 22, ni 33, ni 55, ni 77, ni 1111 ne divise 247247, mais 247=13×19247 = 13 \times 19. Donc 247247 est composé.

Pour 251251 : les restes par 22, 33, 55, 77, 1111 et 1313 sont 11, 22, 11, 66, 99 et 44. Aucun n'est nul : 251251 est premier.

Attention1 n'est pas premier, et impair ne veut pas dire premier

✗ « 3939 est impair et ne finit pas par 55, donc il est premier. »

✓ 39=3×1339 = 3 \times 13 est composé. Être impair élimine seulement le diviseur 22. Seul le test des nombres premiers pp tels que p2≤np^{2} \leq n permet de conclure. Et 11 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)