Sciences

La décomposition en facteurs premiers

Dossier - Merveilleux nombres premiers
DossierClassé sous :Mathématiques , nombre premier , Merveilleux nombres premiers

Vedettes des mathématiques, les nombres premiers, divisibles uniquement par un et par eux-mêmes, continuent d’occuper les mathématiciens de tous horizons. Découvrez les propriétés et l’histoire de ces nombres essentiels en cryptographie dans ce dossier.

  
DossiersMerveilleux nombres 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è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 nq 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 = 22 x 52

123.456.789 = 32 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 = 210

65.000 = 2 x 2 x 2 x 5 x 5 x 5 x 5 x 13 = 23 x 54 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 672 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).