La décomposition en facteurs premiers

Comme tout nombre entier supérieur à 1 est divisible par au moins un nombre premier, on comprend de façon intuitive que l'on peut ramener tout nombre entier à un produit où ne figurent que des nombres premiers : en effet, si un nombre composé figurait dans ce produit, on pourrait à son tour le décomposer pour faire apparaître un diviseur premier, etc.

Ces mystérieux nombres premiers. © Sakkmesterke, Fotolia

Cette proposition est énoncée ci-dessous sous la forme d'un « théorèmethéorème de décomposition en facteurs premiers », parfois nommé « théorème fondamental de l'arithmétique ». Les Grecs le connaissaient, bien qu'ils n'en aient pas donné de démonstration complète.

Iouri Matiassevitch (ici en 1969) est l’auteur avec Boris Stechkin d’un crible géométrique qui met notamment en évidence les nombres premiers. © Wikimedia Commons, CC by 3.0

Produits de nombres premiers

Tout nombre entier supérieur à 1 s'écrit de manière unique (à l'ordre près) sous la forme d'un produit de nombres premiers.

Contentons-nous pour l'instant de démontrer l'existence de cette décomposition pour tout nombre entier. Nous allons utiliser pour cela la forme 2 du raisonnement par récurrence.

Initialisation : 2 s'écrit comme produit de nombres premiers, car 2 = 2 (par convention, un nombre seul est considéré comme un produit d'un facteur).
Soit n un entier supérieur à 2. Supposons que tous les entiers entre 2 et n - 1 s'écrivent comme produit de nombres premiers (hypothèse de récurrence), et montrons que cela est aussi vrai pour n.

Nous savons (d'après la proposition selon laquelle tout nombre supérieur à 1 est divisible par un nombre premier) que n est divisible par un nombre premier p. Donc n = q x p avec 1 p ≤ n.

• Si p = n (et q = 1), c'est terminé, car le nombre premier p est un produit de nombres premiers.
• Si p est inférieur à n, alors q est compris entre 2 et n - 1 et, d'après l'hypothèse de récurrence, q est un produit de nombres premiers. Par conséquent, n l'est aussi, puisqu'il est le produit de q par le nombre premier p. Cela clôt la démonstration.

Ce théorème de décomposition en facteurs premiers se traduit immédiatement en algorithme pour la décomposition des nombres et la recherche de leurs diviseurs :

• tenter toutes les divisions de a par les nombres premiers entre 2 et √a ;
• dès qu'un facteur premier p est trouvé, mémoriser p, diviser a par p, ce qui donne un nouveau nombre a, puis reprendre l'algorithme avec ce nouveau nombre ;
• si aucun diviseur n'est trouvé, c'est que a est premier ; l'ajouter à la liste ;
• la liste des nombres premiers ainsi constituée est la décomposition du nombre a initial en facteurs premiers ; en combinant ces facteurs de toutes les façons possibles, on obtient les diviseurs de a.

Le crible géométrique de Matiassevitch. © Belin

Par exemple, décomposons a = 220 à l'aide de l'algorithme :

• dès la première division, on trouve p = 2 ; a devient 220/2 = 110 ;
• dès la deuxième division, on trouve p = 2 ; a devient 110/2 = 55 ;
• à la troisième division, on trouve p = 5 ; a devient 55/5 = 11 ;
• comme 11 est premier, on s'arrête ;
• la liste des facteurs premiers de 220, obtenue au bout de seulement cinq divisions, est 2, 2, 5, 11 ;
• la liste des diviseurs de 220 est donc : 1 ; 2 ; 5 ; 11 ; 2 x 2 ; 2 x 5 ;
• 2 x 11 ; 5 x 11 ; 2 x 2 x 5 ; 2 x 2 x 11 ; 2 x 5 x 11 ; 2 x 2 x 5 x 11.

Quelques exemples de décompositions en facteurs premiers

1.111.111 = 239 x 4.649

100 = 2 x 2 x 5 x 5 = 2² x 5²

123.456.789 = 3² x 3.803 x 3.607

1.024 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 2¹⁰

65.000 = 2 x 2 x 2 x 5 x 5 x 5 x 5 x 13 = 2³ x 5⁴ x 13

1.515.151.515.151.515 = 3 x 5 x 17 x 73 x 101 x 137 x 5.882.353

23.571.113.171.923.293.137 = 7 x 67² x 151 x 4.967.701.595.369

1.000.000.000.000.000.000.000.001 = 17 x 9.999.999.900.000.001 x 5.882.353

95.647.806.479.275.528.135.733.781.266.203.904.794.419.563.064.407 = 
95.647.806.479.275.528.135.733.781.266.203.904.794.419.563.064.407 (il s'agit d'un nombre premier).