Calculatrice de décomposition en facteurs premiers

Dernière mise à jour : 2026-05-19

Décomposition en facteurs premiers

Tout entier supérieur à 1 peut s'écrire comme produit de nombres premiers. Cette représentation s'appelle la décomposition en facteurs premiers. Par exemple :

$360 = 2^3 \cdot 3^2 \cdot 5$

Les nombres 2, 3 et 5 sont les « atomes » de 360 — ils ne peuvent pas être divisés davantage. Les exposants (3, 2 et 1) indiquent combien de fois chaque nombre premier apparaît dans le produit.

Le Théorème fondamental de l'arithmétique

Le Théorème fondamental de l'arithmétique garantit deux choses :

1. Existence : Tout entier supérieur à 1 possède au moins une décomposition en facteurs premiers.
2. Unicité : Cette décomposition est unique à l'ordre des facteurs près.

Pourquoi 1 n'est-il pas premier ? Si 1 était premier, il y aurait une infinité de décompositions différentes pour le même entier (360 = 1 · 2³ · 3² · 5 = 1² · 2³ · 3² · 5, etc.). Exclure 1 des nombres premiers est précisément ce qui préserve l'unicité.

La division d'essai pas à pas

La méthode la plus directe est la division d'essai : on teste successivement tous les entiers de 2 à $\sqrt{n}$ comme diviseurs potentiels.

Exemple avec n = 360 :

1. Divisible par 2 ? Oui : 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45. 45 est impair ; plus de 2. Facteur 2³.
2. Divisible par 3 ? Oui : 45 ÷ 3 = 15, 15 ÷ 3 = 5. 5 n'est pas divisible par 3. Facteur 3².
3. Divisible par 5 ? Oui : 5 ÷ 5 = 1. Facteur 5¹.
4. Le quotient est 1 — terminé. Résultat : $360 = 2^3 \cdot 3^2 \cdot 5$.

Pourquoi s'arrêter à $\sqrt{n}$ ? Si n a un facteur premier p > $\sqrt{n}$, alors n/p < $\sqrt{n}$, ce qui signifie qu'un facteur plus petit existe nécessairement. Si aucun diviseur n'est trouvé jusqu'à $\sqrt{n}$, alors n est lui-même premier.

L'arbre des facteurs

Un arbre des facteurs est une représentation visuelle : on décompose un nombre en deux facteurs quelconques, et on répète jusqu'à ce que toutes les branches aboutissent à des nombres premiers.

         360
        /    \
       8      45
      / \    /  \
     4   2  9    5
    / \    / \
   2   2  3   3

Les feuilles donnent 2, 2, 2, 3, 3, 5 → 2³ · 3² · 5. Quelle que soit la façon de construire l'arbre, on aboutit toujours au même résultat — c'est l'unicité en action.

Compter les diviseurs grâce à la décomposition

Une fois la décomposition connue, le nombre total de diviseurs positifs se calcule avec une seule formule :

$\tau(n) = (e_1+1)(e_2+1)\cdots(e_k+1)$

Pourquoi cette formule ? Tout diviseur de $n$ est obtenu en choisissant indépendamment, pour chaque facteur premier $p_i^{e_i}$, un exposant entier $k$ tel que $0 \le k \le e_i$ — soit $e_i+1$ choix par facteur premier. Comme les choix sont indépendants, les quantités se multiplient.

Diviseurs de 360 :

$\tau(360) = (3+1)(2+1)(1+1) = 4 \cdot 3 \cdot 2 = 24$

Le nombre 360 possède exactement 24 diviseurs positifs.

PGCD et PPCM via la décomposition

En connaissant les décompositions de deux nombres, on lit directement leur PGCD et leur PPCM :

• PGCD : prendre l'exposant minimal pour chaque nombre premier.
• PPCM : prendre l'exposant maximal pour chaque nombre premier.

Exemple : PGCD et PPCM de 360 et 504

$360 = 2^3 \cdot 3^2 \cdot 5, \qquad 504 = 2^3 \cdot 3^2 \cdot 7$

Premier	Exp. 360	Exp. 504	min (PGCD)	max (PPCM)
2	3	3	3	3
3	2	2	2	2
5	1	0	0	1
7	0	1	0	1

$\text{PGCD}(360, 504) = 2^3 \cdot 3^2 = 72, \qquad \text{PPCM}(360, 504) = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$

Simplifier les fractions

Pour réduire $\dfrac{a}{b}$ à sa forme irréductible, on divise numérateur et dénominateur par $\text{PGCD}(a, b)$ :

$\frac{360}{504} = \frac{360 \div 72}{504 \div 72} = \frac{5}{7}$

Applications de la décomposition en facteurs premiers

Domaine	Utilisation
Cryptographie (RSA)	La sécurité repose sur la difficulté de factoriser le produit de deux grands nombres premiers
Tables de hachage	Des tailles premières minimisent les collisions
Théorie des codes	Polynômes générateurs des codes correcteurs d'erreurs
Musique (gamme juste)	Les intervalles sont des rapports de puissances de 2, 3 et 5

Cas particuliers

• n = 2 (le plus petit premier) : La décomposition est 2 ; exactement 2 diviseurs.
• n est premier : Un seul facteur premier ; nombre de diviseurs = 2.
• Puissance d'un premier (ex. 1024 = 2¹⁰) : Un seul premier avec un grand exposant ; 11 diviseurs.
• Nombres hautement composés (360, 720, 1260…) : Ont plus de diviseurs que tout nombre strictement inférieur.

Récapitulatif

Notion	Formule
Décomposition	$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$
Nombre de premiers distincts	$\omega(n) = k$
Nombre de diviseurs	$\tau(n) = \prod (e_i + 1)$
PGCD de deux nombres	produit avec exposants minimaux
PPCM de deux nombres	produit avec exposants maximaux
Identité PGCD × PPCM	$\text{PGCD}(a,b) \times \text{PPCM}(a,b) = a \times b$

Questions fréquentes (FAQ)

Qu'est-ce que la décomposition en facteurs premiers ?

La décomposition en facteurs premiers consiste à écrire un entier supérieur à 1 comme produit de nombres premiers. Par exemple, 360 = 2³ · 3² · 5. Le Théorème fondamental de l'arithmétique garantit que cette représentation est unique (à l'ordre des facteurs près), ce qui en fait la base de la divisibilité et de nombreux algorithmes en cryptographie.

Pourquoi la décomposition en facteurs premiers est-elle unique ?

Le Théorème fondamental de l'arithmétique stipule que tout entier supérieur à 1 admet une décomposition en facteurs premiers unique, à l'ordre près. Cette unicité est ce qui permet de définir sans ambiguïté le PGCD et le PPCM de deux entiers, et ce qui fonde la sécurité du chiffrement RSA.

Comment compter les diviseurs à partir de la décomposition ?

Si n = p₁^e₁ · p₂^e₂ · … · pₖ^eₖ, le nombre de diviseurs positifs est τ(n) = (e₁+1)(e₂+1)…(eₖ+1). Pour 360 = 2³ · 3² · 5¹, τ(360) = 4 · 3 · 2 = 24 : 360 possède exactement 24 diviseurs positifs.

Quel est le plus grand nombre que cette calculatrice peut décomposer ?

Cette calculatrice prend en charge les entiers jusqu'à 1 000 000 000 000 (10¹², un billion). Elle utilise la division d'essai jusqu'à √n, ce qui nécessite au plus un million d'itérations — suffisant pour s'exécuter rapidement dans le navigateur. Pour des nombres plus grands, on recourt à des algorithmes spécialisés comme la méthode rho de Pollard ou le crible quadratique.