Calculatrice de facteurs premiers

360 = 2^3 * 3^2 * 5 ; Ω(360) = 3 + 2 + 1 = 6 ; d(360) = (3+1) * (2+1) * (1+1) = 24

n

Le nombre que l’on casse — un entier de 1 à 1 000 000. Cette plage est celle que le module d’arithmétique utilise partout, elle coïncide donc exactement avec la page des facteurs et un lecteur qui passe de l’une à l’autre retrouve les mêmes bords. Les nombres décimaux sont refusés plutôt qu’arrondis, et 0 comme les négatifs sont refusés parce que la décomposition en facteurs premiers est un énoncé portant sur des entiers positifs

p

Un facteur premier — un nombre premier qui divise n exactement. La page les trouve par divisions successives dans l’ordre croissant, donc le plus petit nombre premier est toujours extrait en premier et la décomposition imprimée va toujours du plus petit nombre premier au plus grand. Pour 360 les nombres premiers sont 2, 3 et 5, et aucun autre ne le divise

e

L’exposant d’un nombre premier — combien de fois ce nombre premier apparaît dans le produit. 360 vaut 2 × 2 × 2 × 3 × 3 × 5, donc 2 apparaît trois fois et 3 deux fois. Un nombre premier qui n’apparaît qu’une fois est imprimé sans aucun exposant : le 5 de 360 s’écrit 5 et non 5^1, ce qui est la convention habituelle et garde les décompositions courtes lisibles

2^3 * 3^2 * 5

La décomposition de 360 telle qu’elle est imprimée, et la saisie par défaut. L’accent circonflexe tient lieu d’exposant et l’astérisque de multiplication, donc l’ensemble survit à un copier-coller dans un champ de texte brut ou dans une barre de recherche. Il existe exactement une telle expression pour tout entier supérieur à 1, et c’est ce qui la rend digne d’être imprimée : 360 ne peut pas s’écrire aussi comme un autre produit de nombres premiers

Ω(360) = 3 + 2 + 1 = 6

Le nombre de facteurs premiers en comptant les répétitions : trois 2, deux 3 et un 5 font six. C’est le compte qui surprend, parce que 360 donne l’impression d’être construit à partir de trois nombres premiers et non de six. La recette est d’additionner les exposants plutôt que de compter les nombres premiers distincts, et les deux réponses diffèrent dès qu’un exposant dépasse 1

d(360) = (3+1) * (2+1) * (1+1) = 24

Le nombre de diviseurs positifs, obtenu à partir des mêmes exposants en ajoutant un à chacun puis en multipliant. La liste est 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180 et 360 — vingt-quatre en tout. C’est une autre question que celle du dessus : elle compte les nombres qui divisent 360, et non les nombres premiers qui le construisent

La décomposition est ce que vous voulez quand la question porte sur la structure multiplicative d’un nombre plutôt que sur sa taille. Simplifier une fraction ou une racine carrée en est le cas quotidien : la racine carrée de 72 se simplifie en 6√2 parce que 72 = 2³ × 3², et l’exposant de chaque nombre premier dit quelle part peut sortir de sous le radical — c’est la même décomposition que lit la page des radicaux. Trouver un plus grand commun diviseur ou un plus petit commun multiple de deux nombres, c’est encore cela, fait une fois par nombre : les nombres premiers partagés à leur plus petit exposant donnent le premier, et tous les nombres premiers à leur plus grand exposant donnent le second. Les questions de divisibilité se traitent de la même façon, puisqu’un nombre en divise un autre exactement quand ses nombres premiers et leurs exposants sont tous disponibles dans l’autre. En arithmétique, la décomposition tranche si un nombre est premier, combien de diviseurs il a, s’il est un carré parfait (tous les exposants pairs) et s’il est un cube parfait. Le théorème fondamental de l’arithmétique est précisément ce qui autorise tout ce qui précède : sans l’unicité de la décomposition, l’imprimer ne serait qu’une curiosité et non une réponse. Les limites de la méthode valent aussi d’être connues : la division par essais est rapide sur un million et sans espoir sur un nombre à cent chiffres, et c’est exactement cet écart entre facile et difficile qui porte la cryptographie à clé publique. Quand la question est de savoir quels nombres divisent le vôtre plutôt que quels nombres premiers le construisent, la page des facteurs les liste ; quand elle est de savoir si le nombre est premier, la page des nombres premiers y répond directement.

1. Le cas par défaut : 360

   1. 360 est pair, on divise donc par 2 : 360 / 2 = 180, puis 180 / 2 = 90, puis 90 / 2 = 45 — trois fois en tout
   2. 45 n’est pas pair ; le nombre premier suivant est 3, et 45 / 3 = 15, puis 15 / 3 = 5 — deux fois
   3. 5 est premier, donc la décomposition est 2 × 2 × 2 × 3 × 3 × 5, qui s’écrit 2^3 * 3^2 * 5
   4. On compte les facteurs premiers avec les répétitions : 3 + 2 + 1 = 6
   5. On compte les diviseurs à partir des exposants : (3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24

   La saisie par défaut, et celle qui montre pourquoi les deux comptes sont imprimés du tout. Six et vingt-quatre se font face, et un lecteur qui s’attend à ce qu’ils coïncident croira que l’un des deux est cassé. Ils ne le sont pas : six est le nombre de pièces premières dont le nombre est fait quand on garde chaque répétition, et vingt-quatre est le nombre de nombres qui le divisent. L’écart entre les deux vient des exposants — chaque répétition d’un nombre premier multiplie le nombre de diviseurs sans beaucoup ajouter au nombre de pièces. Vérifiez l’un ou l’autre à la main et le calcul est court ; vérifiez les deux et vous vous souviendrez de qui est qui.

2. Le petit cas qui montre l’écart : 12

   1. 12 / 2 = 6, et 6 / 2 = 3, donc 2 apparaît deux fois
   2. 3 est premier, donc la décomposition est 2^2 * 3
   3. On compte les facteurs premiers avec les répétitions : 2 + 1 = 3, soit 2, 2 et 3
   4. On liste les diviseurs : 1, 2, 3, 4, 6, 12 — six en tout
   5. On vérifie par la recette : (2 + 1) × (1 + 1) = 3 × 2 = 6, ce qui correspond à la liste

   L’exemple réduit le plus net de la confusion autour de laquelle cette page est construite, parce que les deux comptes sont assez petits pour être vérifiés à la main en quelques secondes. Douze est fait de trois nombres premiers — 2, 2 et 3 — et six nombres le divisent. Lire la sortie comme « 3 diviseurs » ou comme « 6 facteurs premiers » sonne plausible dans les deux cas, et les deux sont faux. La liste des diviseurs montre aussi l’appariement qui rend six pair : 1 avec 12, 2 avec 6, 3 avec 4. Douze n’est pas un carré parfait, donc aucun diviseur ne s’apparie avec lui-même, et c’est pourquoi le compte est pair.

3. Le cas embarrassant : 1

   1. 1 n’est divisible par aucun nombre premier — le diviser par 2, 3, 5 ou n’importe quel autre laisse une fraction
   2. Il n’y a donc aucun facteur premier, et leur compte vaut 0
   3. Le seul nombre positif qui divise 1 est 1 lui-même, donc le nombre de diviseurs vaut 1
   4. La décomposition s’imprime comme le chiffre 1 plutôt que comme un champ vide

   Le cas qu’il faut décider plutôt que dériver, et la décision est d’imprimer 1. Laisser la décomposition vide se lirait comme un échec de calcul, ce qui est la seule chose qu’un panneau de résultat ne doit jamais avoir l’air d’être. Les deux comptes tombent alors honnêtement : aucun nombre premier, et un diviseur. Un n’est ni premier ni composé — c’est l’élément neutre de la multiplication, le nombre qui ne change rien quand on multiplie par lui — et la page ne prétend pas le contraire. Il est accepté plutôt que refusé parce que la plage d’entrée commence à 1, et une plage qui exclurait sa propre borne basse serait plus étrange à expliquer.

L’entrée doit être un entier de 1 à 1 000 000. Zéro est refusé : tout nombre premier divise zéro, le produit devrait donc être infini. Les nombres négatifs sont refusés pour une raison voisine — les nombres premiers les divisent encore, mais le signe doit être porté séparément et l’énoncé d’unicité de la décomposition porte sur les nombres positifs. Les nombres décimaux sont refusés plutôt qu’arrondis, puisque arrondir répondrait silencieusement à une question portant sur un autre nombre. Le plafond d’un million vient du module d’arithmétique partagé et relève du coût plutôt que de l’exactitude : la division par essais sur tous les nombres premiers jusqu’à la racine carrée est rapide à un million et sans espoir sur un nombre à vingt chiffres. C’est une vraie frontière de la méthode, et c’est la même frontière qui fait fonctionner la cryptographie à clé publique. La page rapporte la décomposition et deux comptes, rien d’autre : elle ne liste pas les diviseurs eux-mêmes, ne calcule ni plus grand commun diviseur ni plus petit commun multiple sur plusieurs nombres, et ne simplifie ni radicaux ni fractions. Un exposant de 1 n’est jamais imprimé, donc un nombre premier qui n’apparaît qu’une fois se montre à nu, et le signe de multiplication est un astérisque partout, ce qui veut dire que la sortie est du texte brut sans séparateur de milliers. Enfin, le tableau de référence plus bas montre quatre nombres figés au lieu de suivre votre saisie.

Quelle est la différence entre les deux comptes de cette page ?

Le premier compte les facteurs premiers en gardant les répétitions, le second compte les diviseurs. Pour 12 les réponses sont 3 et 6, et les deux sont justes. Douze vaut 2 × 2 × 3, il est donc fait de trois pièces premières ; et 1, 2, 3, 4, 6 et 12 le divisent tous, il a donc six diviseurs. La confusion est naturelle parce que les deux nombres sont proches sur les petites entrées. La recette du premier est d’additionner les exposants ; celle du second est d’ajouter un à chaque exposant puis de multiplier. C’est cette multiplication qui fait que le second compte s’envole tellement plus vite — chaque répétition supplémentaire d’un nombre premier multiplie le nombre de diviseurs tout en n’ajoutant qu’un au premier.

N’y a-t-il qu’une seule décomposition en facteurs premiers pour un nombre ?

Oui, et c’est un théorème plutôt qu’une convention. Tout entier supérieur à 1 peut s’écrire comme un produit de nombres premiers, et il n’y a exactement qu’une façon de le faire une fois l’ordre ignoré. Trois cent soixante n’est jamais que 2³ × 3² × 5 ; il n’est pas aussi un autre produit de nombres premiers. Ce résultat s’appelle le théorème fondamental de l’arithmétique, et sans lui imprimer une décomposition serait une curiosité et non une réponse. C’est aussi pourquoi la page peut imprimer le plus petit nombre premier en premier en étant sûre que c’est la forme canonique — l’ordre est choisi pour la lisibilité, et rien n’est perdu à le fixer.

Que fait la page du nombre 1 ?

Elle imprime 1 comme décomposition, avec zéro facteur premier et un diviseur. Un n’est ni premier ni composé : il n’a pas de décomposition en facteurs premiers au sens habituel, et le théorème ci-dessus est énoncé pour les nombres supérieurs à 1 pour cette raison même. Mais un panneau de résultat vide se lirait comme un échec de calcul, donc la page imprime le chiffre et rapporte les deux comptes honnêtement. Le nombre de diviseurs de 1 vaut réellement 1, puisque le seul nombre positif qui divise 1 est 1 lui-même, et le nombre de facteurs premiers vaut réellement 0. Un est accepté plutôt que refusé parce que la plage d’entrée commence à 1, et refuser la borne basse de sa propre plage demande plus d’explications que d’y répondre.

Pourquoi la page s’arrête-t-elle à un million ?

Parce que la méthode est la division par essais, et que son coût croît comme la racine carrée du nombre. Trouver les nombres premiers d’un nombre proche d’un million demande de tester les diviseurs jusqu’à mille, ce qui est instantané. Trouver ceux d’un nombre à vingt chiffres demande de tester jusqu’à dix milliards, ce qui ne l’est pas. Cet écart n’est pas un détail d’implémentation — c’est une propriété réelle du problème, et c’est l’hypothèse sur laquelle repose la cryptographie à clé publique, où la difficulté de factoriser de grands nombres est ce qui garde un message secret. En dessous d’un million, toutes les réponses reviennent immédiatement, et le plafond est annoncé dans la saisie plutôt que caché dans un délai d’attente.

Quand voudrais-je une décomposition plutôt qu’une liste de facteurs ?

Quand la question porte sur la structure plutôt que sur l’appartenance. Simplifier la racine carrée de 72 exige 72 = 2³ × 3², parce que les exposants disent quelle part de chaque nombre premier peut sortir de sous le radical, ce qui donne 6√2. Trouver un plus grand commun diviseur entre deux nombres exige les deux décompositions, puisque la réponse est faite des nombres premiers partagés à leur plus petit exposant. Vérifier qu’un nombre est un carré parfait se lit d’un coup d’œil sur les exposants — tous pairs veut dire oui. Lister les diviseurs est une autre question, et selon le nombre la réponse peut être bien plus longue : 720 720 en a 240, ce qui fait beaucoup à imprimer et pas grand-chose à regarder. La page des facteurs de ce site les liste quand c’est cela dont vous avez besoin.

Pourquoi aucun exposant n’est-il imprimé quand un nombre premier n’apparaît qu’une fois ?

Parce qu’écrire 5^1 pour un 5 tout seul est du bruit. La convention en mathématiques est d’imprimer un exposant seulement lorsqu’il est supérieur à un, donc 360 s’écrit 2^3 * 3^2 * 5 avec le dernier terme à nu. Rien n’est perdu à l’enlever : l’absence d’exposant signifie que l’exposant vaut un, sans ambiguïté, et une décomposition faite uniquement de nombres premiers simples — ce qu’a un nombre sans facteur carré — se lit comme un produit ordinaire sans le moindre accent circonflexe. C’est la même convention qui fait que 97, qui est premier, s’imprime comme 97 et non comme 97^1.

• Prime Factorization — writing a whole number as a product of primes, and the algorithms that find the primes — Wolfram MathWorld (United States)
• Fundamental Theorem of Arithmetic — the statement that every whole number above 1 has exactly one prime factorization, which is what makes printing it worth doing — Wolfram MathWorld (United States)
• Divisor Function — the count of positive divisors, the formula that builds it from the exponents, and how it behaves on powers of a single prime — Wolfram MathWorld (United States)
• Théorème fondamental de l’arithmétique — l’unicité de la décomposition en facteurs premiers, les exposants, le nombre de diviseurs et le cas particulier de 1 — Wikipédia en français