Nombre premier et décomposition
Testez la primalité d’un entier et obtenez sa décomposition en facteurs premiers et son nombre de diviseurs.
Comment ce calcul a-t-il été fait ?
Test de primalité par division d'essai : On teste les diviseurs de 2 à √12. Le plus petit diviseur trouvé montre que 12 est composé. Décomposition en facteurs premiers : 12 = 2^2 × 3. Nombre de diviseurs = (2 + 1) × (1 + 1) = 6.
Nombres premiers et décomposition en facteurs premiers
Un nombre premier est un entier strictement supérieur à 1 qui n’admet que deux diviseurs : 1 et lui-même. Ainsi 2, 3, 5, 7, 11 et 13 sont premiers, tandis que 4, 6, 8 ou 9 ne le sont pas, car ils possèdent d’autres diviseurs. Les nombres premiers sont en quelque sorte les briques élémentaires de l’arithmétique : on ne peut pas les décomposer davantage. Le nombre 1, lui, n’est par convention ni premier ni composé, car il n’a qu’un seul diviseur.
Leur importance vient du théorème fondamental de l’arithmétique : tout entier supérieur à 1 s’écrit de manière unique, à l’ordre des facteurs près, comme un produit de nombres premiers. Par exemple, 12 = 2 x 2 x 3, ce que l’on note 2² x 3. Cette décomposition est le point de départ d’innombrables calculs : simplification de fractions, recherche du PGCD et du PPCM, et même la cryptographie moderne qui sécurise les paiements en ligne.
Cet outil teste instantanément si un entier est premier et fournit sa décomposition complète en facteurs premiers, le nombre exact de ses diviseurs, ainsi que le détail de la méthode employée (division d’essai jusqu’à la racine carrée). Saisissez un entier positif et obtenez la réponse en direct.
Formules
p premier <=> p > 1 et diviseurs(p) = {1, p}Un nombre premier possède exactement deux diviseurs distincts : 1 et lui-même. Cette définition exclut 1 (un seul diviseur) et tous les nombres composés (au moins trois diviseurs). Le plus petit nombre premier est 2, et c’est aussi le seul nombre premier pair : tout autre nombre pair est divisible par 2, donc composé.
tester les diviseurs d de 2 à √nPour savoir si n est premier, il suffit de chercher un diviseur entre 2 et la racine carrée de n. Inutile d’aller plus loin : si n avait un diviseur supérieur à √n, son cofacteur serait inférieur à √n et aurait déjà été trouvé. Si aucun diviseur n’est trouvé jusqu’à √n, alors n est premier. Cette borne réduit énormément le nombre de tests.
n = p1^a1 x p2^a2 x ... x pk^akLe théorème fondamental de l’arithmétique garantit que cette écriture existe et qu’elle est unique (à l’ordre des facteurs près). Les p sont des nombres premiers distincts et les exposants a sont des entiers strictement positifs. On l’obtient en divisant successivement n par ses plus petits facteurs premiers jusqu’à atteindre 1.
d(n) = (a1 + 1) x (a2 + 1) x ... x (ak + 1)Une fois la décomposition connue, le nombre total de diviseurs s’obtient en ajoutant 1 à chaque exposant puis en multipliant le tout. Chaque diviseur correspond en effet à un choix d’exposant entre 0 et a pour chaque facteur premier. Cette formule compte tous les diviseurs, y compris 1 et n lui-même.
rayer les multiples de chaque premier jusqu’à √NPour dresser la liste de tous les nombres premiers jusqu’à un entier N, on écrit les entiers de 2 à N, puis on raye successivement les multiples de 2, de 3, de 5, etc. Les nombres qui restent sont premiers. C’est une méthode très efficace, attribuée au savant grec Eratosthène, pour générer des tables de premiers.
Exemples
On veut vérifier rapidement si 7 est un nombre premier, à la main, par division d’essai.
Racine carrée de 7 environ 2,65 : il suffit de tester les diviseurs 2
7 divisé par 2 ne tombe pas juste (7 est impair)
Aucun entier de 2 à 2 ne divise 77 est premier. Sa décomposition est 7 et il a 2 diviseurs : 1 et 7.
Pour les petits nombres, la racine carrée limite les tests à très peu de candidats. C’est tout l’intérêt de la borne √n.
On cherche la décomposition de 12 et son nombre de diviseurs.
12 est pair : 12 = 2 x 6
6 est pair : 6 = 2 x 3, donc 12 = 2 x 2 x 3
3 est premier : on s’arrête. 12 = 2² x 312 = 2² x 3. Nombre de diviseurs = (2 + 1) x (1 + 1) = 6.
Les six diviseurs sont 1, 2, 3, 4, 6 et 12. La décomposition donne donc à la fois la structure du nombre et le compte exact de ses diviseurs.
Le nombre 100 revient souvent (pourcentages, conversions). Quelle est sa décomposition ?
100 = 2 x 50 = 2 x 2 x 25
25 = 5 x 5, donc 100 = 2 x 2 x 5 x 5
On regroupe : 100 = 2² x 5²100 = 2² x 5². Nombre de diviseurs = (2 + 1) x (2 + 1) = 9.
Les neuf diviseurs sont 1, 2, 4, 5, 10, 20, 25, 50 et 100. Cette décomposition sert directement à simplifier des fractions comme 100/360.
91 ressemble à un nombre premier (impair, ne se termine pas par 5), mais l’apparence trompe.
On teste les diviseurs jusqu’à √91 environ 9,5
91 n’est pas divisible par 2, 3, 5
91 = 7 x 13 : un diviseur est trouvé91 = 7 x 13. Il est composé, avec 4 diviseurs : 1, 7, 13 et 91.
C’est un piège classique : un nombre peut sembler premier mais être le produit de deux premiers proches. Seule la division d’essai jusqu’à √n tranche avec certitude.
Cas d’usage
Le chiffrement RSA, qui protège les paiements bancaires et les communications, repose sur la difficulté de décomposer un très grand nombre en deux facteurs premiers. Multiplier deux grands premiers est facile ; retrouver ces facteurs à partir du produit est pratiquement impossible avec les moyens actuels. Les nombres premiers sont ainsi au cœur de la sécurité numérique.
Pour réduire une fraction à sa forme irréductible, on décompose le numérateur et le dénominateur en facteurs premiers, puis on supprime les facteurs communs. Par exemple, 12/18 devient 2/3 après simplification par 6. La décomposition rend cette opération systématique et sans erreur.
Le plus grand commun diviseur (PGCD) et le plus petit commun multiple (PPCM) de deux nombres se lisent directement sur leurs décompositions : on prend les facteurs premiers communs au plus petit exposant pour le PGCD, et tous les facteurs au plus grand exposant pour le PPCM. Indispensable pour additionner des fractions ou synchroniser des cycles.
La primalité, la décomposition et le crible d’Eratosthène sont au programme du collège et du lycée. Cet outil vérifie une décomposition, compte les diviseurs et détaille la méthode, ce qui permet de contrôler un exercice et de comprendre chaque étape du raisonnement.
Les tables de hachage, les générateurs de nombres pseudo-aléatoires et de nombreux algorithmes utilisent des nombres premiers pour mieux répartir les valeurs et éviter les collisions. Savoir tester rapidement la primalité est une brique de base en programmation.