Nombres premiers et décomposition en facteurs premiers

Un nombre premier est un entier naturel qui a exactement deux diviseurs : 1 et lui-même. 2, 3, 5, 7, 11 et 13 sont premiers ; 1 ne l'est pas (un seul diviseur), 12 non plus (divisible par 2, 3, 4, 6). Tout entier supérieur ou égal à 2 s'écrit de façon unique comme un produit de nombres premiers : c'est sa décomposition en facteurs premiers. Ce chapitre montre comment tester si un nombre est premier, comment trouver tous les nombres premiers jusqu'à une limite avec le crible d'Ératosthène, comment décomposer un entier et en déduire tous ses diviseurs.

Définition et premiers exemples

Les 25 nombres premiers inférieurs à 100 :

Retiens au moins ceux qui sont inférieurs à 30 : ils servent dans tous les tests et toutes les décompositions.

Il y a une infinité de nombres premiers. Euclide l'a démontré il y a plus de 2 000 ans : si on n'en avait qu'un nombre fini, on pourrait les multiplier tous et ajouter 1 ; le résultat ne serait divisible par aucun d'eux, ce qui est contradictoire. Les plus grands nombres premiers connus comptent plusieurs dizaines de millions de chiffres.

Tester si un nombre est premier

Pour savoir si un entier n ≥ 2 est premier, on cherche un diviseur entre 2 et n − 1. Mais il suffit de chercher jusqu'à √n :

Pourquoi ? Si n = a × b avec a ≤ b, alors a × a ≤ a × b = n, donc a ≤ √n : un nombre composé a toujours un diviseur inférieur ou égal à sa racine carrée. Et il suffit de tester les nombres premiers : si 4 divisait n, 2 le diviserait déjà.

Exemple 1 : 223 est-il premier ? √223 ≈ 14,9. On teste les nombres premiers 2, 3, 5, 7, 11 et 13 :

Aucun diviseur jusqu'à 13, et 17 > √223 : 223 est premier.

Exemple 2 : 221 est-il premier ? √221 ≈ 14,9. 2, 3, 5, 7 et 11 ne le divisent pas, mais 221 = 13 × 17 : 221 n'est pas premier. Cet exemple montre qu'un nombre composé peut n'avoir que de « grands » diviseurs : il faut aller au bout des tests.

Le crible d'Ératosthène

Pour trouver tous les nombres premiers jusqu'à une limite N, le crible d'Ératosthène (IIIᵉ siècle avant notre ère) évite de tester chaque nombre :

1. écris tous les entiers de 2 à N ;
2. le premier nombre non barré, 2, est premier : barre tous ses multiples à partir de 2 × 2 = 4 ;
3. le nombre suivant non barré, 3, est premier : barre tous ses multiples à partir de 3 × 3 = 9 ;
4. continue avec le nombre suivant non barré (5, puis 7…) ;
5. arrête-toi dès que le carré du nombre suivant dépasse N : tous les nombres non barrés sont premiers.

Pourquoi commencer à barrer à p × p ? Les multiples plus petits de p (2p, 3p…) ont déjà été barrés comme multiples de 2, de 3, etc. Et pourquoi s'arrêter quand p² > N ? Pour la même raison que dans le test : un nombre composé inférieur à N a un diviseur premier inférieur ou égal à √N.

Le crible est l'algorithme le plus efficace pour lister les petits nombres premiers ; il se programme en quelques lignes (chapitre 11).

Décomposer un entier en produit de facteurs premiers

La méthode : divise n par le plus petit nombre premier qui le divise, recommence avec le quotient, et continue jusqu'à obtenir 1. On présente souvent le calcul en deux colonnes.

Exemple : 360.

360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5.

Exemple : 1 980. 1 980 = 2 × 990 = 2² × 495 ; 495 = 5 × 99 (il se termine par 5) ; 99 = 9 × 11 = 3² × 11. Donc 1 980 = 2² × 3² × 5 × 11.

Exemple : 2 026. 2 026 = 2 × 1 013. Est-ce que 1 013 est premier ? √1 013 ≈ 31,8 : on teste 3, 5, 7, 11, 13, 17, 19, 23, 29 et 31, aucun ne divise 1 013. Donc 1 013 est premier, et 2 026 = 2 × 1 013.

Lister tous les diviseurs d'un entier

La décomposition donne tous les diviseurs d'un coup : un diviseur de n = 2³ × 3² × 5 est un produit 2ᵃ × 3ᵇ × 5ᶜ, avec a entre 0 et 3, b entre 0 et 2 et c entre 0 et 1. Chaque exposant ne peut pas dépasser celui de n.

Il y a 4 choix pour a, 3 pour b et 2 pour c : 360 a donc 4 × 3 × 2 = 24 diviseurs. En général :

Exemple : les diviseurs de 72 = 2³ × 3². 72 a (3 + 1)(2 + 1) = 12 diviseurs. On les range dans un tableau à double entrée : une ligne par puissance de 2, une colonne par puissance de 3, chaque case contenant le produit.

Les diviseurs de 72 sont : 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.

Pour trois facteurs premiers, on fait un tableau pour les deux premiers, puis on multiplie chaque case par chaque puissance du troisième, ou on dessine un arbre.

Reconnaître des entiers premiers entre eux

Deux entiers a et b sont premiers entre eux s'ils n'ont aucun diviseur commun autre que 1, c'est-à-dire si leur PGCD vaut 1 (chapitre 7). Avec les décompositions, c'est immédiat : ils sont premiers entre eux s'ils n'ont aucun facteur premier en commun.

• 26 = 2 × 13 et 9 = 3² : aucun facteur commun, 26 et 9 sont premiers entre eux. Pourtant aucun des deux n'est premier.
• 26 = 2 × 13 et 8 = 2³ : le facteur 2 est commun, ils ne sont pas premiers entre eux.
• Deux nombres premiers distincts sont toujours premiers entre eux, et deux entiers consécutifs aussi (un diviseur commun diviserait leur différence, 1).

Cette notion est au cœur du chiffrement affine : la clé a doit être première avec 26.

Où servent les nombres premiers en informatique

• Chiffrement asymétrique. Le chiffrement RSA, encore utilisé pour signer une grande partie des certificats des sites HTTPS, repose sur un fait simple : multiplier deux grands nombres premiers est facile, retrouver ces deux nombres à partir de leur produit est extrêmement long. Une clé RSA de 2 048 bits est le produit de deux nombres premiers d'environ 1 024 bits chacun (environ 309 chiffres décimaux chacun, et un produit de 617 chiffres). Le détail de RSA est hors programme ; le cours de cryptographie le déroule pas à pas avec de petits nombres.
• Tables de hachage. Une table de hachage range une donnée de clé k dans la case k mod m. On choisit souvent pour m un nombre premier, pour que les données se répartissent bien même si les clés suivent un motif régulier (chapitre 9).
• Générateurs pseudo-aléatoires et sommes de contrôle utilisent aussi des modules premiers.

Exercices

Exercice 1 sur 5 Premier ou pas ? Réussi À revoir

Dis si chaque nombre est premier. Si non, donne un diviseur autre que 1 et lui-même. Justifie.

1. 97
2. 91
3. 437
4. 561
5. 1 001

Voir la réponseMasquer la réponse de l'exercice 1

1. √97 ≈ 9,8 : on teste 2, 3, 5 et 7. 97 est impair, 9 + 7 = 16 n'est pas multiple de 3, il ne se termine ni par 0 ni par 5, 97 = 7 × 13 + 6. 97 est premier.
2. 91 = 7 × 13, il n'est pas premier.
3. √437 ≈ 20,9 : 2, 3, 5, 7, 11, 13 et 17 ne divisent pas 437, mais 437 = 19 × 23. Il n'est pas premier.
4. 5 + 6 + 1 = 12 est un multiple de 3 : 561 = 3 × 187 = 3 × 11 × 17. Il n'est pas premier.
5. 1 001 = 7 × 143 = 7 × 11 × 13. Il n'est pas premier. Le critère de 11 le montre aussi : 1 − 0 + 0 − 1 = 0.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 2 sur 5 Le crible jusqu'à 100 Réussi À revoir

1. Jusqu'à quel nombre premier faut-il barrer les multiples pour cribler les entiers jusqu'à 100 ? Justifie.
2. Combien y a-t-il de nombres premiers entre 50 et 100 ? Donne-les.

Voir la réponseMasquer la réponse de l'exercice 2

1. Il faut barrer les multiples des nombres premiers p tels que p² ≤ 100, soit p ≤ 10 : 2, 3, 5 et 7. Le suivant, 11, a pour carré 121 > 100.
2. Il y en a 10 : 53, 59, 61, 67, 71, 73, 79, 83, 89 et 97.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 3 sur 5 Décompositions Réussi À revoir

Décompose en produit de facteurs premiers.

1. 84
2. 1 155
3. 3 600
4. 4 096

Voir la réponseMasquer la réponse de l'exercice 3

1. 84 = 2 × 42 = 2 × 2 × 21 = 2² × 3 × 7.
2. 1 155 se termine par 5 : 1 155 = 5 × 231 ; 2 + 3 + 1 = 6 : 231 = 3 × 77 = 3 × 7 × 11. 1 155 = 3 × 5 × 7 × 11.
3. 3 600 = 36 × 100 = (2² × 3²) × (2² × 5²) = 2⁴ × 3² × 5².
4. 4 096 = 2¹² : 4 096 = 2¹². On le reconnaît dans la table des puissances de 2 (2¹⁰ = 1 024, 2¹¹ = 2 048, 2¹² = 4 096).

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 4 sur 5 Nombre de diviseurs Réussi À revoir

1. Combien 3 600 a-t-il de diviseurs ?
2. Liste les diviseurs de 84 avec un tableau.
3. Combien de diviseurs a une puissance de 2, 2ⁿ ? Lesquels ?

Voir la réponseMasquer la réponse de l'exercice 4

1. 3 600 = 2⁴ × 3² × 5² : (4 + 1)(2 + 1)(2 + 1) = 5 × 3 × 3 = 45 diviseurs.

2. 84 = 2² × 3 × 7 a (2 + 1)(1 + 1)(1 + 1) = 12 diviseurs. Tableau des diviseurs de 2² × 3 = 12, puis multiplication par 7 :

   ×	1	3
   1	1	3
   2	2	6
   4	4	12

   Diviseurs de 12 : 1, 2, 3, 4, 6, 12. Multipliés par 7 : 7, 14, 21, 28, 42, 84. Les diviseurs de 84 sont 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84.

3. 2ⁿ a n + 1 diviseurs : 1, 2, 4, …, 2ⁿ, c'est-à-dire toutes les puissances de 2 jusqu'à 2ⁿ.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 5 sur 5 Premiers entre eux Réussi À revoir

Les couples suivants sont-ils formés d'entiers premiers entre eux ? Justifie avec les décompositions.

1. 15 et 26
2. 21 et 35
3. 2 026 et 1 013
4. 255 et 256

Voir la réponseMasquer la réponse de l'exercice 5

1. 15 = 3 × 5 et 26 = 2 × 13 : aucun facteur commun, premiers entre eux.
2. 21 = 3 × 7 et 35 = 5 × 7 : facteur commun 7, pas premiers entre eux.
3. 2 026 = 2 × 1 013 : 1 013 divise 2 026, pas premiers entre eux (leur PGCD est 1 013).
4. 255 = 3 × 5 × 17 et 256 = 2⁸ : aucun facteur commun, premiers entre eux. C'est normal : deux entiers consécutifs le sont toujours.

Tu avais trouvé ?

Oui, j'avais bonPas encore