Nombres premiers et décomposition en facteurs premiers : tester jusqu'à √n, puis tout factoriser

Ce chapitre appartient à la partie arithmétique de l'option maths expertes de terminale. Le programme (BO spécial n° 8 du 25 juillet 2019) y range trois résultats : l'ensemble des nombres premiers est infini, dont la démonstration est exigible ; la décomposition d'un entier en produit de facteurs premiers existe et est unique ; le petit théorème de Fermat, traité avec les congruences.

Le plus petit diviseur d'un entier est premier

Propriété 1. Tout entier n ≥ 2 admet au moins un diviseur premier : son plus petit diviseur d strictement supérieur à 1. En effet, si d n'était pas premier, il aurait un diviseur d′ avec 1 < d′ < d, et d′ diviserait aussi n, ce qui contredit le choix de d.

Propriété 2. Si n ≥ 2 n'est pas premier, son plus petit diviseur premier p vérifie p² ≤ n. On écrit n = p × m avec m ≥ 2. Or m ≥ 2 admet un diviseur premier q (propriété 1) ; q divise aussi n, donc q ≥ p, et m ≥ q ≥ p. Ainsi n = pm ≥ p².

La contraposée donne le test : si aucun nombre premier p avec p² ≤ n ne divise n, alors n est premier. On teste donc les nombres premiers jusqu'à √n, ni moins ni plus.

Décider si un nombre est premier

Exemple 1 · 211 est premier, 221 ne l'est pas

Rédaction. 14² = 196 et 15² = 225, donc 14 < √211 < 15. Les nombres premiers à tester sont 2, 3, 5, 7, 11 et 13. 211 est impair ; la somme de ses chiffres, 4, n'est pas multiple de 3 ; il ne finit ni par 0 ni par 5 ; 211 = 7 × 30 + 1, 211 = 11 × 19 + 2 et 211 = 13 × 16 + 3. Aucun ne divise 211 : 211 est premier.

Pour 221, la même liste s'applique, puisque 14² < 221 < 15². 2, 3, 5, 7 et 11 ne le divisent pas, mais 221 = 13 × 17. Le nombre 221 n'est pas premier. L'élève qui conclut « premier » après avoir testé jusqu'à 11 seulement se trompe.

Pour obtenir tous les nombres premiers jusqu'à une borne, le crible d'Ératosthène, au programme parmi les algorithmes, applique la propriété 2 à tous les entiers à la fois. La figure le déroule jusqu'à 100. Le 1 est barré d'office. On entoure 2 et l'on barre ses multiples à partir de 4, puis on entoure 3 et l'on barre ses multiples à partir de 9, puis 5 à partir de 25, puis 7 à partir de 49. On commence à p² parce que les multiples kp avec k < p ont déjà été barrés à cause d'un facteur premier de k, plus petit que p. Au moment de passer à 11, 11² = 121 dépasse 100 : tout entier composé inférieur ou égal à 100 a déjà un facteur premier au plus égal à 7. Les 25 cases restantes, colorées en or à la dernière étape, sont les nombres premiers inférieurs à 100.

Une infinité de nombres premiers

Théorème. L'ensemble des nombres premiers est infini.

Démonstration, par l'absurde. Supposons qu'il n'y ait qu'un nombre fini de nombres premiers, p₁, p₂, …, pₖ. Posons N = p₁ × p₂ × … × pₖ + 1. Comme N ≥ 2, N admet un diviseur premier p (propriété 1), qui est l'un des pᵢ. Alors p divise le produit p₁ × … × pₖ et divise N, donc il divise leur différence, 1. C'est impossible, puisque p ≥ 2. L'hypothèse est fausse : il existe une infinité de nombres premiers.

La preuve n'affirme pas que N est premier. Avec les six premiers nombres premiers, 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30 031 = 59 × 509. Ce que dit la preuve, c'est que N a un facteur premier hors de la liste, ici 59 et 509.

Décomposer en produit de facteurs premiers

Théorème. Tout entier n ≥ 2 s'écrit n = p₁^α₁ × p₂^α₂ × … × pₖ^αₖ, où p₁ < p₂ < … < pₖ sont des nombres premiers et α₁, …, αₖ des entiers naturels non nuls. Cette écriture est unique.

L'existence se prouve par récurrence forte : n a un diviseur premier p ; si n = p, c'est fini, sinon n/p est compris entre 2 et n − 1 et se décompose déjà. L'unicité repose sur une conséquence du théorème de Gauss : si un nombre premier divise un produit, il divise l'un des facteurs. Le programme ne range ni l'une ni l'autre parmi les démonstrations exigibles.

Méthode. On divise par 2 tant que c'est possible, puis par 3, puis par 5, 7, 11…, en notant chaque quotient, et l'on s'arrête quand le quotient est 1 ou quand le carré du diviseur testé dépasse le quotient restant, qui est alors premier.

Exemple 2 · Les diviseurs de 360, puis PGCD(360 ; 84)

Rédaction. 360 = 2 × 180 = 2² × 90 = 2³ × 45 = 2³ × 3² × 5. Un diviseur positif de 360 s'écrit 2ᵃ × 3ᵇ × 5ᶜ avec a ∈ {0, 1, 2, 3}, b ∈ {0, 1, 2}, c ∈ {0, 1}, et l'unicité de la décomposition garantit que deux choix différents donnent deux diviseurs différents. 360 a donc 4 × 3 × 2 = 24 diviseurs positifs.

84 = 2² × 3 × 7. Les facteurs communs sont 2 et 3, avec les plus petits exposants 2 et 1 : PGCD(360 ; 84) = 2² × 3 = 12. Le 5 et le 7 n'apparaissent que d'un côté et ne comptent pas. Pour de grands nombres, l'algorithme d'Euclide va plus vite.

Exemple 3 · Rendre 360 carré parfait

Énoncé. Trouver le plus petit entier k ≥ 1 tel que 360k soit le carré d'un entier.

Rédaction. Si 360k = m², la décomposition de m² a des exposants pairs, et par unicité c'est celle de 360k. Dans 360 = 2³ × 3² × 5, les exposants de 2 et de 5 sont impairs : k doit contenir au moins un facteur 2 et un facteur 5, donc k est un multiple de 10. Pour k = 10, 3 600 = 2⁴ × 3² × 5² = (2² × 3 × 5)² = 60². Le plus petit k est 10.

Où les copies se trompent sur les nombres premiers

• « 1 est premier ». Il n'a qu'un diviseur positif.
• Le test arrêté avant √n, ou mené jusqu'à n/2 en perdant son temps.
• Une décomposition qui garde un facteur non premier : 360 = 2³ × 9 × 5 n'est pas finie.
• Dans la preuve de l'infinité, l'affirmation que p₁ × … × pₖ + 1 est premier.
• Le nombre de diviseurs calculé α₁ × α₂ × … au lieu de (α₁ + 1)(α₂ + 1)…

Trois exercices corrigés sur les nombres premiers

Exercice 1 · 391 est-il premier ?

Correction. 19² = 361 et 20² = 400, donc on teste les premiers jusqu'à 19 : 2, 3, 5, 7, 11, 13, 17, 19. 391 est impair, la somme de ses chiffres vaut 13, il ne finit ni par 0 ni par 5, et 7, 11, 13 ne le divisent pas. En revanche 391 = 17 × 23. 391 n'est pas premier.

Exercice 2 · Combien de diviseurs pour 1 386 ?

Correction. 1 386 = 2 × 693 = 2 × 3 × 231 = 2 × 3² × 77 = 2 × 3² × 7 × 11. Le nombre de diviseurs positifs est (1 + 1)(2 + 1)(1 + 1)(1 + 1) = 24.

Exercice 3 · Si 2ⁿ − 1 est premier, n est premier

Énoncé. Soit n ≥ 2. Montrer que si 2ⁿ − 1 est premier, alors n est premier. La réciproque est-elle vraie ?

Correction. On montre la contraposée. Supposons n non premier : n = ab avec 2 ≤ a ≤ n − 1 et 2 ≤ b. Comme 2ᵃ ≡ 1 [2ᵃ − 1], on a 2ⁿ = (2ᵃ)ᵇ ≡ 1 [2ᵃ − 1], donc 2ᵃ − 1 divise 2ⁿ − 1. Explicitement, 2ᵃᵇ − 1 = (2ᵃ − 1)(1 + 2ᵃ + 2²ᵃ + … + 2⁽ᵇ⁻¹⁾ᵃ). Or 3 ≤ 2ᵃ − 1 < 2ⁿ − 1 : 2ⁿ − 1 a un diviseur autre que 1 et lui-même, il n'est pas premier. Par exemple 2⁶ − 1 = 63 = 7 × 9, avec a = 3 et b = 2.

La réciproque est fausse : 11 est premier, mais 2¹¹ − 1 = 2 047 = 23 × 89.