Facteurs premiers

Décomposition en facteurs premiers : l'empreinte que chaque nombre possède une seule fois

Tout entier supérieur à 1 est un produit de nombres premiers et — c'est ce qui le rend utile — il l'est d'une seule façon. Le théorème fondamental de l'arithmétique garantit l'unicité, d'où son rôle d'empreinte et d'où tant de constructions qui s'appuient dessus, de la réduction des fractions à la cryptographie à clé publique.

Comment ça marche

• Décompose un nombre en facteurs premiers, en puissances et développé en entier.
• Compte les diviseurs sans les énumérer, directement à partir des exposants.
• Indique si le nombre est premier, ce qui est simplement le cas où il se décompose en lui-même.

every integer above 1 factorises into primes in exactly one way

  360 = 2 x 2 x 2 x 3 x 3 x 5
      = 2^3 x 3^2 x 5

the number of divisors follows from the exponents
  d(n) = (3 + 1) x (2 + 1) x (1 + 1) = 24

Exemple chiffré

Décomposer 360 en retirant à répétition le plus petit facteur premier qui convient.

1. 360 / 2 = 180
2. 180 / 2 = 90
3. 90 / 2 = 45 2 appears three times
4. 45 / 3 = 15
5. 15 / 3 = 5 3 appears twice
6. 5 / 5 = 1 5 appears once
7. result 2^3 x 3^2 x 5

360 = 2³ × 3² × 5, et aucune autre combinaison de premiers ne donne 360. Des seuls exposants découle le nombre de diviseurs : (3+1)(2+1)(1+1) = 24, car tout diviseur choisit 0 à 3 deux, 0 à 2 trois et 0 ou 1 cinq.

Lire le résultat

• La formule des diviseurs vaut à elle seule le détour. On n'a jamais besoin de les lister pour les compter : ajoutez un à chaque exposant et multipliez, car construire un diviseur revient à choisir indépendamment combien de chaque premier y entrent.
• La division d'essai n'a besoin de tester que jusqu'à la racine carrée. Si n a un facteur supérieur à √n, il a forcément le facteur associé en dessous : passé la racine, il ne reste rien à trouver. D'où l'instantanéité sur un nombre à six chiffres.
• Après 2 et 3, l'outil avance de six en six et ne teste que 6k−1 et 6k+1. Tous les autres restes sont déjà divisibles par 2 ou 3, ce qui écarte gratuitement deux tiers des candidats.
• Que la factorisation soit difficile pour de très grands nombres est une propriété, pas une limite de cet outil. RSA repose sur le fait que multiplier deux grands premiers est facile et les retrouver ne l'est pas : cette asymétrie constitue tout l'argument de sécurité.

Questions fréquentes

1 est-il premier ?

Non, et l'exclure est un choix délibéré, non un oubli. Si 1 comptait comme premier, les décompositions cesseraient d'être uniques — 6 vaudrait 2×3, ou 1×2×3, ou 1×1×2×3 — et le théorème qui rend la factorisation utile réclamerait une exception malcommode dans chaque énoncé.

Pourquoi mon nombre ne se décompose-t-il qu'en lui-même ?

Parce qu'il est premier. Un nombre premier n'a d'autres diviseurs que 1 et lui-même : sa décomposition est un terme unique d'exposant un. L'outil le dit explicitement plutôt que de vous le laisser déduire d'une liste à un élément.