Comment Faire la Factorisation en Nombres Premiers
La factorisation en nombres premiers consiste à écrire un entier comme un produit de nombres premiers, les seules briques qui ne se divisent plus en dessous d’elles-mêmes. Elle sert à simplifier une fraction, lister tous les diviseurs d’un nombre, ou comprendre la difficulté de calcul sur laquelle repose une bonne partie du chiffrement moderne. Une fois la méthode maîtrisée sur un petit nombre à la main, elle se généralise à n’importe quelle valeur entière.
La division par essais à la main
La méthode la plus simple à exécuter sur papier s’appelle la division par essais. On divise le nombre par le plus petit nombre premier possible, 2, autant de fois que la division tombe juste. On passe ensuite au nombre premier suivant, 3, puis 5, 7, 11, et ainsi de suite, jusqu’à ce que le quotient obtenu vaille 1.
Prenons 360 comme exemple.
- 360 est pair, on divise par 2 : 360 ÷ 2 = 180.
- 180 est encore pair : 180 ÷ 2 = 90.
- 90 est encore pair : 90 ÷ 2 = 45.
- 45 n’est plus divisible par 2, il est impair. On teste le nombre premier suivant, 3 : 45 ÷ 3 = 15.
- 15 se divise encore par 3 : 15 ÷ 3 = 5.
- 5 est lui-même premier, donc 5 ÷ 5 = 1. Le quotient vaut 1, on s’arrête là.
| Étape | Division | Quotient obtenu |
|---|---|---|
| 1 | 360 ÷ 2 | 180 |
| 2 | 180 ÷ 2 | 90 |
| 3 | 90 ÷ 2 | 45 |
| 4 | 45 ÷ 3 | 15 |
| 5 | 15 ÷ 3 | 5 |
| 6 | 5 ÷ 5 | 1 |
En rassemblant les diviseurs utilisés, on obtient trois fois le facteur 2, deux fois le facteur 3, et une fois le facteur 5. Cela donne 360 = 2 × 2 × 2 × 3 × 3 × 5, qu’on écrit plus proprement sous forme d’exposants : 360 = 2^3 × 3^2 × 5. La vérification est rapide : 2^3 = 8, 3^2 = 9, et 8 × 9 × 5 = 360.
Un exemple plus grand : 997 est-il premier ?
Pour tester si un nombre est premier, il n’est pas nécessaire d’essayer tous les diviseurs jusqu’au nombre lui-même. Dès que le carré du diviseur testé dépasse le nombre qu’on cherche à factoriser, on peut s’arrêter : si aucun diviseur plus petit que la racine carrée n’a fonctionné, il n’y en aura pas non plus au-delà, puisque les diviseurs d’un nombre se répartissent toujours en paires symétriques de part et d’autre de sa racine carrée.
Prenons 997. Sa racine carrée vaut environ 31,6, donc il suffit de tester les nombres premiers jusqu’à 31 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 et 31.
- 997 est impair, donc pas divisible par 2.
- La somme de ses chiffres, 9 + 9 + 7 = 25, n’est pas un multiple de 3.
- Il ne se termine ni par 0 ni par 5, donc pas divisible par 5.
- 997 ÷ 7 : 7 × 142 = 994, reste 3, pas divisible.
- 997 ÷ 11 : 11 × 90 = 990, reste 7, pas divisible.
- 997 ÷ 13 : 13 × 76 = 988, reste 9, pas divisible.
- 997 ÷ 17 : 17 × 58 = 986, reste 11, pas divisible.
- 997 ÷ 19 : 19 × 52 = 988, reste 9, pas divisible.
- 997 ÷ 23 : 23 × 43 = 989, reste 8, pas divisible.
- 997 ÷ 29 : 29 × 34 = 986, reste 11, pas divisible.
- 997 ÷ 31 : 31 × 32 = 992, reste 5, pas divisible.
Aucun de ces nombres premiers ne divise 997 exactement, et le prochain candidat, 37, donne déjà 37² = 1369, largement au-dessus de 997. Inutile d’aller plus loin : 997 est premier.
Calculez avec vos propres nombres
N'importe quel nombre entier jusqu'à 1 000 000 000 000. Le signe est ignoré.
Saisissez un nombre entier pour voir sa factorisation en nombres premiers et ses diviseurs.
- Facteurs premiers distincts
- —
- Nombre de diviseurs
- —
Usages réels : simplifier une fraction et la cryptographie
Pour simplifier une fraction, il suffit de factoriser le numérateur et le dénominateur séparément, puis d’annuler les facteurs premiers qu’ils ont en commun. Prenons 84/126. Le nombre 84 se factorise en 2^2 × 3 × 7, et 126 se factorise en 2 × 3^2 × 7. Les deux partagent un facteur 2, un facteur 3 et un facteur 7, soit un facteur commun de 2 × 3 × 7 = 42. En divisant le numérateur et le dénominateur par 42, on obtient 84 ÷ 42 = 2 et 126 ÷ 42 = 3, donc 84/126 se réduit à 2/3. Cette méthode fonctionne pour n’importe quelle fraction, même avec de grands nombres, et elle évite de chercher le plus grand diviseur commun par tâtonnement.
La même décomposition donne aussi directement tous les diviseurs d’un nombre. Pour 360 = 2^3 × 3^2 × 5, chaque diviseur s’obtient en combinant une puissance de 2 entre 0 et 3, une puissance de 3 entre 0 et 2, et une puissance de 5 entre 0 et 1. Cela fait (3 + 1) × (2 + 1) × (1 + 1) = 24 combinaisons possibles, donc 360 possède exactement 24 diviseurs, de 1 à 360 lui-même.
Les grands nombres premiers sont aussi au cœur du chiffrement RSA, qui sécurise une bonne partie du trafic internet. Le principe repose sur une asymétrie de difficulté : multiplier deux grands nombres premiers est rapide, même pour un ordinateur modeste, mais retrouver ces deux facteurs à partir du seul produit devient extrêmement lent dès que les nombres dépassent quelques centaines de chiffres. RSA part de deux nombres premiers p et q, souvent longs de plus de 150 chiffres chacun, et construit sa clé publique autour de leur produit n = p × q. Casser cette clé reviendrait à factoriser n, un calcul qui prendrait des milliers d’années aux meilleurs algorithmes connus sur du matériel classique. C’est exactement cet écart entre la facilité de multiplier et la difficulté de factoriser qui rend le système sûr.
Erreurs courantes et cas limites
Quelques pièges reviennent souvent quand on factorise à la main.
0 et 1 ne sont ni premiers ni composés. Un nombre premier a exactement deux diviseurs distincts, 1 et lui-même. Le nombre 1 n’a qu’un seul diviseur, lui-même, donc il ne remplit pas la condition. Le nombre 0, lui, est divisible par tout entier non nul, ce qui ne correspond à aucune factorisation en nombres premiers définie.
Un nombre négatif se factorise sur sa valeur absolue. Le signe n’entre pas dans la décomposition : -12 se factorise comme 12, soit 2^2 × 3, et le signe se traite à part.
La règle d’arrêt de la division par essais. Comme pour 997 plus haut, dès que le carré du diviseur testé dépasse ce qui reste à factoriser, ce reste est forcément premier. Continuer à tester des diviseurs plus grands ne change rien au résultat, ça ne fait que perdre du temps.
| Nombre | Factorisation | Statut |
|---|---|---|
| 0 | non définie | ni premier ni composé |
| 1 | aucun facteur premier | ni premier ni composé |
| -12 | 2^2 × 3 (valeur absolue) | composé |
| 17 | 17 | premier |
| 360 | 2^3 × 3^2 × 5 | composé |
| 997 | 997 | premier |
Questions fréquentes
À quoi sert la factorisation en nombres premiers ? Elle sert à simplifier des fractions en annulant les facteurs communs au numérateur et au dénominateur, à lister tous les diviseurs d’un nombre à partir de ses exposants, et à comprendre la difficulté de calcul derrière des systèmes de chiffrement comme RSA, qui reposent sur des produits de grands nombres premiers difficiles à refactoriser.
Comment savoir si un nombre est premier rien qu’en le regardant ? Quelques vérifications rapides éliminent beaucoup de cas : un nombre pair plus grand que 2 est toujours composé, un nombre qui se termine par 0 ou 5 (sauf 5 lui-même) est divisible par 5, et si la somme de ses chiffres est un multiple de 3, le nombre l’est aussi. Au-delà de ces raccourcis, il n’existe pas de méthode visuelle universelle : il faut passer par la division par essais jusqu’à la racine carrée, comme dans l’exemple de 997 plus haut.
Quel est le plus grand nombre que je peux factoriser à la main ? Ça dépend surtout de la patience et du temps disponible. La division par essais reste gérable à la main jusqu’à quelques milliers, tant que la racine carrée du nombre reste petite. Au-delà, tester tous les diviseurs premiers devient long et source d’erreurs de calcul, et un calculateur devient nettement plus fiable.
Le calculateur peut-il gérer de très grands nombres ? Oui, il factorise n’importe quel entier jusqu’à 1 000 000 000 000 (mille milliards) en gardant le calcul quasi instantané, puisqu’il applique la même division par essais jusqu’à la racine carrée, mais exécutée par la machine plutôt qu’à la main.