Sciences

L’unicité de 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
 

Ce théorème « clé » est ce qui nous manquait pour prouver enfin le résultat d'unicité de la décomposition en facteurs premiers. Le théorème de l'unicité de la décomposition en facteurs premiers s'énonce ainsi : tout nombre entier n supérieur à 1 s'écrit de manière unique (à l'ordre près) comme produit de nombres premiers.

Qu'est-ce que le théorème de l'unicité de la décomposition en facteurs premiers ? © Futura

Nous allons démontrer l'unicité de cette décomposition en effectuant un raisonnement par récurrence de type 2.

Le théorème est évidemment vrai pour n = 2. Considérons alors un nombre n supérieur à 2, et faisons l'hypothèse que tout nombre entier entre 2 et n - 1 possède un développement unique en facteurs premiers. Si nous parvenons à prouver que c'est aussi le cas pour n, le théorème sera démontré par récurrence. Afin de prouver que n se décompose de façon unique en un produit de facteurs premiers, on doit montrer que deux produits de facteurs premiers égaux à n sont nécessairement identiques à l'ordre près des facteurs. Notons q1q2...qm et s1s2...sp ces deux produits et considérons leurs premiers facteurs respectifs q1 et s1.

  • Cas 1 : si q1s1, on simplifie de chaque côté de l'égalité : q1q2...qms1s2...sp qui devient : q2...qms2...sp

Les deux nouveaux produits q2...qm et s2...sp sont nécessairement égaux à un entier inférieur à n. On utilise alors l'hypothèse de récurrence (« tout nombre entier entre 2 et n - 1 possède un développement unique en facteurs premiers ») pour conclure que les décompositions q2...qm et s2...sp sont les mêmes à l'ordre près. Comme q1s1, les deux décompositions initiales q1q2...qm et s1s2...sp étaient donc, elles aussi, identiques à l'ordre près.

  • Cas 2 : supposons que q1 est différent de s1.

L'égalité q1q2...qms1s2...spsignifie que le nombre premier q1 divise le produit des deux nombres s1 et (s2...sp). D'autre part, q1 ne divise pas s1, puisque deux nombres premiers différents n'ont, par définition, pas de facteurs communs autres que 1. En appliquant le théorème clé de l'arithmétique, on conclut que q1, s'il ne divise pas s1, divise s2...sp. Ce produit ks2...sp est inférieur à n : par conséquent, l'hypothèse de récurrence s'applique (« tout nombre entier entre 2 et n - 1 possède un développement unique en facteurs premiers »), et l'on conclut que la décomposition s2...sp du nombre k est unique. Comme le nombre premier q1 divise k, il est nécessairement l'un des facteurs premiers du produit s2...sp.

Une représentation des facteurs communs des nombres inférieurs à 100. © Belin

Comparer plusieurs décompositions

Reprenons alors l'égalité q1q2...qms1s2...sp pour la simplifier par q1 de chaque côté. Les deux nouveaux produits de facteurs premiers sont égaux à un même nombre inférieur à n, et l'hypothèse de récurrence s'applique de nouveau, indiquant que les facteurs premiers sont (à l'ordre près) identiques de part et d'autre. Les deux décompositions initiales q1q2...qm et s1s2...sp étaient donc les mêmes à l'ordre près. En prouvant le cas 2 à la suite du cas 1, nous venons d'achever la démonstration de l'unicité.

Même si l'ordre des facteurs n'importe pas dans une décomposition en facteurs premiers, on doit être capable de s'y retrouver lorsqu'on compare plusieurs décompositions. Dorénavant, quand nous traiterons d'un nombre n ≥ 2 quelconque, nous écrirons sa décomposition en facteurs premiers en classant les nombres premiers par ordre croissant, par exemple p1 = 2, p2 = 3, p3 = 3, etc., et en regroupant les facteurs identiques. Ainsi, la décomposition du nombre 120 s'écrit :
120 = 2 x 2 x 2 x 3 x 5 = 23 x 31 x 51

L'exposant d'un nombre premier pi, facteur d'un nombre n, est nommé la multiplicité de pi dans la décomposition de n.

Nous serons parfois amenés à écrire des multiplicités nulles. Une telle notation est utile quand on doit traiter simultanément plusieurs nombres, car on fait alors apparaître les mêmes facteurs premiers dans chaque décomposition ; par exemple, 20 = 22 x 30 x 51 x 110 et 33 = 20 x 31 x 50 x 111. Cette notation permet aussi d'écrire n'importe quel nombre n sous la forme :

(le symbole Π représente le produit) où les pi correspondent à la suite des nombres premiers p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, p6 = 13, etc. Dans ce produit, les nombres premiers qui ne sont pas facteurs du nombre considéré reçoivent une multiplicité ai nulle.

Certains nombres premiers remarquables permettent de réaliser des tours amusants sans difficulté. © Belin

En affirmant l'existence et l'unicité de la décomposition en facteurs premiers, le théorème fondamental de l'arithmétique permet d'énoncer et de démontrer très facilement.