La décomposition en facteurs premiers est au cœur de la théorie des nombres. Le théorème fondamental de l’arithmétique garantit que tout entier supérieur à 1 possède une décomposition unique en facteurs premiers — les éléments constitutifs irréductibles à partir desquels tous les autres nombres sont assemblés.
Division d’essai et crible d’Ératosthène
La décomposition en facteurs premiers est au cœur de la théorie des nombres. Le théorème fondamental de l’arithmétique garantit que tout entier supérieur à 1 possède une décomposition unique en facteurs premiers — les éléments constitutifs à partir desquels tous les autres nombres sont assemblés. La méthode la plus directe est la division d’essai : divisez le nombre par 2, puis par 3, 5, 7, et ainsi de suite jusqu’à la racine carrée de n. Chaque division réussie donne un facteur premier, et les exposants indiquent combien de fois chaque nombre premier apparaît.
PGCD, PPCM et simplification des fractions avec les facteurs premiers
Le PGCD et le PPCM sont étroitement liés par les décompositions en facteurs premiers. Le PGCD prend le plus petit exposant de chaque facteur premier commun ; le PPCM prend le plus grand. L’algorithme d’Euclide calcule le PGCD bien plus efficacement qu’une décomposition complète — il s’exécute en O(log min(a, b)) étapes, quelle que soit la taille des nombres. Le crible d’Ératosthène est l’algorithme classique pour trouver tous les nombres premiers jusqu’à une limite N. À partir de 2, il marque tous les multiples de chaque nombre premier comme composés. Les nombres non marqués restants sont premiers. Le crible s’exécute en O(N log log N) et reste pratique jusqu’à plusieurs dizaines de millions.
Cryptographie, chiffrement RSA et importance des grands nombres premiers
La décomposition en facteurs premiers est au fondement du chiffrement RSA : avec les algorithmes actuels, il est impossible en pratique de factoriser le produit de deux grands nombres premiers, ce qui garantit la sécurité de la cryptographie à clé publique.