Décomposition en facteurs premiers et test de primalité
Un entier révèle s'il est premier, sa décomposition en facteurs premiers, et la liste de ses diviseurs. Un nombre premier n'a que deux diviseurs : 1 et lui-même — sa décomposition ne comporte alors qu'un seul facteur, à la puissance 1.
Calculatrice
Résultats
| — est-il premier ? | — |
| Décomposition en facteurs premiers | — |
| Nombre de diviseurs positifs | — |
| Somme des diviseurs | — |
| Liste des diviseurs | — |
Comment se calcule une décomposition en facteurs premiers
Division d'essai par 2, 3, 5, 7… jusqu'à √n : chaque diviseur trouvé est un facteur premier
Nombre de diviseurs = produit des (exposant + 1) de chaque facteur premier
Il suffit de tester les diviseurs jusqu'à la racine carrée de n : si aucun facteur premier inférieur ou égal à √n ne divise n, alors n est premier — tout diviseur au-delà aurait un « complément » plus petit déjà testé. Le nombre total de diviseurs se déduit directement des exposants de la décomposition, sans avoir à tous les énumérer.
Les termes marqués d'une étoile se retrouvent glosés dans le lexique.
Premier ou composé : deux tiroirs, pas trois
Un entier plus grand que 1 est premier* s'il n'a que deux diviseurs positifs : 1 et lui-même. On ne le casse pas en un produit de deux entiers plus petits.
2, 3, 5, 7, 11, 13, 17, 19, 23 : c'est le début de la liste, celui qu'on apprend par cœur. 4 n'y figure pas (2 × 2), ni 9 (3 × 3), ni 15 (3 × 5). Ces derniers sont composés*. Pour tout entier ≥ 2, il n'y a pas de troisième tiroir : premier, ou composé. Point. 97 est premier. 360 = 2³ × 3² × 5 ne l'est pas.
Ici, on le lit dans la décomposition. Un seul facteur, à la puissance 1 ? Le nombre est premier. Deux facteurs, ou un exposant plus grand que 1, et il est composé. 9 = 3² n'est pas premier, même s'il n'a qu'un facteur : l'exposant dit déjà 3 × 3. C'est le théorème fondamental de l'arithmétique* en acte : tout entier > 1 s'écrit de façon unique comme produit de premiers, à l'ordre près.
Pourquoi 1 reste à la porte
La question revient tous les ans en classe. 1 n'est divisible que par 1, alors pourquoi pas premier ?
Parce que la définition demande deux diviseurs distincts. 1 n'en a qu'un — lui-même. Il n'est pas composé non plus : on ne le factorise pas en plus petits. Ni premier, ni composé, un statut à part. Le motif profond, c'est l'unicité de l'écriture ci-dessus. Si 1 était premier, on collerait autant de facteurs 1 qu'on voudrait (1 × 1 × 5 = 5) et l'unicité tomberait. Du coup, on l'écarte. Ce n'est pas une lubie de manuel.
Cette page refuse d'ailleurs tout saisi inférieur à 2. Le cas 1 n'a simplement rien à factoriser.
Division d'essai jusqu'à √n : pourquoi la racine suffit
Pour décider si n est premier, on essaie de le diviser par 2, 3, 5, 7… Tant qu'un reste tombe juste, on a un facteur, et n est composé. S'il n'y a aucun facteur jusqu'à √n, n est premier.
Pourquoi s'arrêter à la racine ? Parce que les facteurs vont par paires. Si n = a·b avec a ≤ b, alors a ≤ √n. Un diviseur plus grand que √n aurait son « complément » déjà testé, plus petit. Pour 97, √97 ≈ 9,85. Il suffit d'essayer 2, 3, 5, 7. Aucun ne divise 97, donc 97 est premier. Pour 360, 2 divise dès le premier essai : la question est close, et on continue à diviser le quotient pour vider tous les facteurs.
si aucun premier p ≤ √n ne divise n, alors n est premier
C'est exactement ce que fait cette page, jusqu'à n = 1 milliard (√n ≈ 31 623). Les tests de divisibilité par 2, 3, 5… accélèrent le calcul mental sur de petits n ; la machine, elle, pose le reste, sans reconstituer les critères.
Le crible d'Ératosthène, pour une liste et non pour un seul n
Pour un seul n, la division d'essai jusqu'à √n suffit. Pour tous les premiers jusqu'à une limite N, on change d'outil : le crible d'Ératosthène*.
- Écrire les entiers de 2 à N.
- 2 est premier : barrer tous ses multiples (4, 6, 8…).
- Le premier non barré, 3, est premier : barrer 6, 9, 12…
- Recommencer avec 5, 7, et ainsi de suite, jusqu'à √N. Ce qui n'est pas barré est premier.
Jusqu'à 30, il reste 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Ce n'est pas un test isolé, c'est un balayage. Chaque multiple n'est visité qu'une poignée de fois. En fait, pour remplir une table jusqu'à quelques millions, rien n'est plus simple à programmer. Cette page, elle, répond pour un n : elle ne crible pas tout l'intervalle. Inutile de générer les cinquante millions de premiers sous le milliard pour savoir ce que devient 360.
Ce que les premiers font hors de la classe
Au lycée, on les factorise. Dans une machine, on s'en sert pour cacher de l'information.
La cryptographie à clé publique, RSA en tête, repose sur un produit n = p × q de deux très grands premiers. Multiplier p et q est immédiat. Retrouver p et q à partir de n, sans les connaître, sort des moyens actuels dès que p et q ont quelques centaines de chiffres. C'est le sens de la « clé publique » : on peut afficher n, pas le défaire. On les retrouve aussi dans les tables de hachage (une taille première répartit mieux les collisions), certains générateurs pseudo-aléatoires, des codes correcteurs. Toujours la même idée : modulo un premier, l'arithmétique se comporte bien ; le produit de deux grands premiers, lui, se comporte mal dès qu'on veut le démonter.
Les premiers de cette page n'ont rien à voir avec ceux d'une clé. Ici, on s'arrête à 1 milliard — dix chiffres, un exercice de collège. Un module RSA courant fait 2048 bits, plus de 600 chiffres. Factoriser 360 n'apprend pas à casser une clé.
Jumeaux, Mersenne, et les records de taille
Certains premiers arrivent par paires, à distance 2 : (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (101, 103)… Ce sont les nombres premiers jumeaux. On en connaît d'énormes. On ne sait toujours pas s'il y en a une infinité.
Les nombres de Mersenne* ont la forme 2p − 1. Pour que cette expression soit première, p lui-même doit l'être — nécessaire, pas suffisant. 27 − 1 = 127 est premier. 211 − 1 = 2047 = 23 × 89, et 11 est pourtant premier. Bon, pourquoi s'y intéresser ? Parce que les records de « plus grand premier connu » sont presque toujours des Mersenne : la forme se prête à un test dédié (Lucas–Lehmer), nettement plus efficace que la division d'essai. Le GIMPS, un réseau de machines bénévoles, chasse ces records depuis les années 1990.
Cette page n'ira jamais jusque-là. 219 − 1 = 524 287 tient encore sous le milliard ; le suivant, 231 − 1, explose déjà la borne.
Nombres parfaits : quand les diviseurs propres recollent le tout
Un nombre est parfait* quand la somme de ses diviseurs propres — tous sauf lui-même — le reconstitue.
6 = 1 + 2 + 3. 28 = 1 + 2 + 4 + 7 + 14. Ensuite 496, puis 8 128. La liste s'aère très vite. Tout nombre parfait pair s'écrit 2p−1(2p − 1) dès que 2p − 1 est un premier de Mersenne — c'est le théorème d'Euclide–Euler. On n'a jamais vu de nombre parfait impair. On n'a pas non plus prouvé qu'il n'en existe pas. Les deux questions (existence d'un parfait impair, infinité des parfaits pairs) restent ouvertes, ce qui n'empêche pas 6 et 28 de circuler dans tous les manuels.
Le tableau de cette page additionne tous les diviseurs, y compris n. Un nombre parfait y apparaît donc avec une somme égale à 2n. Pour 28, la case affiche 56. À noter : le nombre de diviseurs, lui, se lit sans les énumérer : si n = pa · qb · …, il y en a (a+1)(b+1)… 360 = 2³ × 3² × 5 en a 4 × 3 × 2 = 24.
nombre de diviseurs = produit des (exposant + 1)
Factoriser pour lire un PGCD ou réduire une fraction
Simplifier une fraction, c'est retirer ce que le numérateur et le dénominateur ont en commun. Ces facteurs communs, c'est exactement le PGCD.
Si a = 2³ × 3² × 5 (soit 360) et b = 2² × 3 × 7 (soit 84), le PGCD prend le min de chaque exposant : 2² × 3 = 12. Le PPCM prend le max : 2³ × 3² × 5 × 7 = 2 520. 360/84 = 30/7 une fois réduit. Pas besoin d'Euclide si les deux décompositions sont déjà là — encore faut-il que les nombres restent assez petits pour les obtenir à la main, ou avec l'outil ci-dessus.
Le calculateur de PGCD et de PPCM travaille dans l'autre sens, par l'algorithme d'Euclide, y compris pour une liste. Le calculateur de fractions s'en sert pour ramener chaque résultat sous forme irréductible. Les deux pages se répondent, dans la même rubrique.
Au-delà du milliard : tester la primalité sans factoriser
Jusqu'à 1 milliard, la division d'essai jusqu'à √n est limpide : √1 000 000 000 ≈ 31 623 essais, un clin d'œil.
Passez à 50 chiffres, et √n en a 25. Personne n'attend 1025 divisions. Pour décider si un monstre est premier, on n'essaie plus de le factoriser. On lance un test de primalité* (Miller–Rabin en pratique, d'autres selon la forme du nombre) qui peut conclure « premier » sans exhiber le moindre facteur. Factoriser, c'est un autre métier, nettement plus dur — c'est même le pari sur lequel repose RSA. Un nombre peut donc être certifié premier alors que personne n'en a dressé la liste des diviseurs, pour la bonne raison que cette liste n'a que deux lignes : 1 et lui-même.
D'où la borne de l'outil : voir une décomposition, pas attaquer un module cryptographique. Un milliard est un plafond honnête : assez grand pour le collège, le lycée, un identifiant, un exercice de concours ; trop petit pour faire croire qu'on factorise une clé. Au-delà de 300 diviseurs, la liste est masquée (certains nombres très composés en ont des milliers) ; le nombre et la somme, eux, restent affichés, déduits des exposants.
2 reste le seul pair de la liste
Tout pair autre que 2 est divisible par 2, donc composé. 2 reste le seul premier pair. C'est presque une lapalissade, et ça raccourcit beaucoup d'arguments.
Dès qu'on cherche des premiers au-delà de 2, on ne regarde plus que les impairs. Le crible commence d'ailleurs par barrer une case sur deux : la parité est le premier filtre, le plus brutal. Les jumeaux, eux, sont presque toujours deux impairs distants de 2 — la paire (2, 3) est le seul couple premier-pair / premier-impair à distance 1, ce qui n'en fait pas des jumeaux. Un entier qui se termine par 0, 2, 4, 6 ou 8, et qui n'est pas égal à 2, n'est pas premier. Inutile d'aller plus loin.
Euclide : il en reste toujours un
Euclide montre qu'il y a une infinité de premiers, sans donner de formule pour le suivant.
On suppose qu'il n'y en a qu'un nombre fini : p1, p2, …, pk. On forme N = p1 × p2 × … × pk + 1. Ce N n'est divisible par aucun des pi (il reste toujours 1). Donc soit N est premier — et il manquait à la liste — soit il a un facteur premier nouveau. Dans les deux cas, la liste était incomplète. On peut recommencer indéfiniment. On ne dit pas comment trouver le prochain. On dit seulement qu'il en reste toujours un.
N = (produit des premiers supposés) + 1 → nouveau premier, ou nouveau facteur
La densité, elle, baisse. Les premiers deviennent plus rares, sans jamais s'arrêter. Entre 1 et 100 il y en a 25 ; entre 1 et 1 000, 168 ; entre 1 et 1 000 000, 78 498. Pas de dernier.
Goldbach : tout pair comme somme de deux premiers ?
Tout entier pair strictement plus grand que 2 serait somme de deux premiers. 4 = 2+2, 6 = 3+3, 8 = 3+5, 10 = 3+7 = 5+5, 28 = 5+23 = 11+17, et ainsi de suite.
On l'a vérifiée par ordinateur jusqu'à des bornes énormes. On ne l'a pas démontrée. C'est une conjecture, pas un théorème : la distinction compte, même si l'énoncé tient en une ligne et qu'aucun contre-exemple n'est jamais sorti. Une version plus faible (tout impair ≥ 7 est somme de trois premiers) a, elle, été prouvée. La version forte, celle qu'on raconte au lycée, reste ouverte. C'est l'un de ces problèmes dont l'énoncé est plus court que n'importe quelle explication de pourquoi on bloque encore.
Cette page ne teste pas Goldbach. Elle factorise un entier. Prendre un pair, le casser, et chercher à la main deux premiers qui le reconstituent, c'est un jeu — pas un certificat de la conjecture. Toute la famille mathématique du site s'arrête, comme ici, là où le calcul reste vérifiable à la main.
Lexique
- Nombre premier
- Entier strictement plus grand que 1, qui n'a que deux diviseurs positifs : 1 et lui-même. 2, 3, 5, 7, 11, 97… Le 1 n'en fait pas partie. La décomposition d'un premier tient en un seul facteur, à la puissance 1.
- Nombre composé
- Entier ≥ 2 qui n'est pas premier, donc produit d'au moins deux premiers (éventuellement égaux). 4, 9, 15, 360. Tout entier ≥ 2 est soit premier, soit composé.
- Théorème fondamental de l'arithmétique
- Tout entier strictement plus grand que 1 s'écrit de façon unique comme produit de nombres premiers, à l'ordre près. C'est cette unicité qui exclut 1 de la liste des premiers.
- Crible d'Ératosthène
- Procédé pour dresser la liste de tous les premiers jusqu'à N : on barre les multiples de 2, puis de 3, puis de chaque entier non barré jusqu'à √N. Ce qui reste est premier. Utile pour une table, pas pour tester un seul n.
- Nombre de Mersenne
- Entier de la forme 2p − 1. Pour qu'il soit premier, p doit l'être (nécessaire, pas suffisant : 211 − 1 = 2047 = 23 × 89). Les records de « plus grand premier connu » sont presque toujours des Mersenne, testés par l'algorithme de Lucas–Lehmer.
- Nombre parfait
- Entier égal à la somme de ses diviseurs propres (tous sauf lui-même). 6, 28, 496, 8 128. Tout parfait pair s'écrit 2p−1(2p − 1) avec 2p − 1 premier de Mersenne (Euclide–Euler). Aucun parfait impair n'est connu.
- Test de primalité
- Procédé qui décide si un entier est premier sans en exhiber les facteurs. Miller–Rabin (probabiliste, très utilisé), AKS (déterministe, plus lourd), Lucas–Lehmer (Mersenne). Distinct de la factorisation, nettement plus difficile.