Mathématiques
Précédent
Suivant
Décomposition en facteurs premiers
Définition

Tout nombre entier positif supérieur ou égal à 2 admet une unique décomposition en produit de facteurs premiers, (à l'ordre d'écriture des facteurs près).

Aujourd'hui des programmes performants peuvent décider en quelques minutes si un nombre d'une centaine de chiffres est premier ou non. Par contre on ne sait pas en un temps raisonnable en faire la décomposition : les algorithmes de cryptage reposent là-dessus.

Existence de la décomposition

On va faire une démonstration par récurrence utilisant la forme forte du principe d'induction.

--- Énoncé de la propriété Le nombre entier positif supérieur ou égal à 2 admet une décomposition en produit de facteurs premiers.

--- Initialisation : le nombre 2 admet de façon évidente une décomposition en produit de facteurs premiers puisqu'il est un nombre premier : est vraie.

--- Hérédité de la propriété : Supposons que est vraie c'est-à-dire que se décompose en produit de facteurs premiers pour tout entier On veut montrer que est vraie, c'est-à-dire que se décompose en produit de facteurs premiers. On constate qu'il y a deux cas, suivant que a est premier ou non.

est un nombre premier

C'est fini, a une décomposition évidente en produit de facteurs premiers.

n'est pas un nombre premier

et On peut appliquer l'hypothèse de récurrence à et qui se décomposent en produit de facteurs premiers, donc se décompose aussi de la même façon.

Donc est vraie si est vraie pour tout entier

--- Conclusion : lorsque la propriété est vraie pour tout nombre entier positif de à elle est vraie aussi pour Comme elle est vraie pour 2, elle est donc vraie pour tous les entiers supérieurs ou égaux à 2.

Unicité de la décomposition

On va encore faire une démonstration par récurrence utilisant la forme forte du principe d'induction.

--- Énoncé de la propriété Le nombre entier positif supérieur ou égal à 2 n'admet qu'une unique décomposition en produit de facteurs premiers, (à l'ordre des facteurs près).

--- Initialisation : de façon évidente, le nombre 2 n'admet qu'une décomposition en produit de facteurs premiers puisqu'il est un nombre premier : est vraie.

--- Hérédité de la propriété : On suppose que cette unicité ait été montrée pour tous les entiers de à On va montrer cette unicité pour l'entier On suppose que l'entier ait deux décompositions :

avec les premiers distincts et les premiers distincts, que l'on suppose rangés en ordre croissant.

On veut montrer que Sinon, on suppose que Alors est distinct de chacun des D'après les propriétés montrées précédemment, si et sont des nombres premiers distincts, est premier avec toute puissance de et est donc premier avec leur produit. Or divise ce qui est contradictoire. On a donc Alors on simplifie l'égalité

par et on applique l'hypothèse de récurrence au nombre inférieur à défini par

Ce nombre admet une unique décomposition en facteurs premiers. Donc les nombres premiers qui figurent dans les deux décompositions sont les mêmes, avec les mêmes exposants.

--- Conclusion : Comme l'unicité de la décomposition est vraie pour 2, parce qu'on sait que si elle est vraie pour tous les entiers de 2 à elle est vraie aussi pour on en conclut que la décomposition en facteurs premiers est unique pour tous les entiers supérieurs ou égaux à 2.

Légende :
Apprendre
S'évaluer
S'exercer
Observer
Simuler
Réalisé avec Scenari (nouvelle fenêtre)