Voici un des résultats les plus importants de l'arithmétique:
Tout nombre n≥2 se décompose en produit de facteurs premiers.
n = p 1 r 1 p 2 r 2 ... p k r k
où tous les nombres pi sont des nombres premiers distincts avec p1 <p2 <...<pk
et où les ri désignent des exposants entiers ≥ 1.
La preuve constitue un excellent cas de récurrence forte.
Le théorème est vrai pour 2. Soit n un entier n >2 si n est premier il n'y a rien à démontrer. Si n n'est pas premier alors on peut écrire
n=pq où p et q  vérifient  (2 ≤ p ≤ n)  ∧ ( 2 ≤ q ≤ n).
On peut donc appliquer l'hypothèse de récurrence forte à p et q, qui sont donc décomposables en produits de facteurs premiers, il en va donc de même pour n.
Cela dit, si p est un facteur (diviseur)  premier de n, p peut à nouveau diviser n/p, c'est à dire qu'en fait rien n'empêche que n soit divisible par p2 , p3 , etc...
Donc, à partir de la décomposition de n en facteurs premiers et en regroupant les facteurs premiers entre eux on arrive à:
n = p 1 r 1 p 2 r 2 ... p k r k
où tous les nombres pi sont des nombres premiers distincts avec p1 <p2 <...<pk
et où les ri désignent des exposants entiers ≥ 1.
C'est cette écriture qu'on appelle 'décomposition de n en produit de facteurs premiers' .
Vous pouvez générer quelques exemples avec le formulaire ci-dessous:
Donner un entier 0< n ≤ 100000
Décomposition de n:
Message d'erreur éventuel:

Le théorème qui suit est d'une utilisation fréquente:
La décomposition d'un nombre en facteurs premiers est unique.
La preuve est très facile en utilisant le théorème dit 'de Bézout' , lequel trouve naturellement sa place dans le chapitre consacré aux entiers relatifs.
Nous la donnerons donc ultérieurement.
En attendant voyons comment s'applique ce théorème d'unicité.
Une égalité telle que:
53 72 =34 73
est obligatoirement fausse car le facteur 5 figure à gauche et pas à droite ou bien parce que 3 figure à droite et pas à gauche.
Une égalité telle que:
54 72 =53 73
est obligatoirement fausse aussi parce que l'exposant de 7 est plus fort à droite, ou bien parce que l'exposant de 5 est plus faible à gauche.

Pour ce qui concerne maintenant la pratique de cette décomposition, les choses sont plus compliquées. Elles peuvent même être très compliquées si le nombre à décomposer est très grand.
Disons que si on repère une factorisation du nombre, on utilisera cette factorisation puis on décomposera chaque facteur. S'il n'existe aucune factorisation évidente, il faut disposer d'une liste de nombres premiers inférieurs ou égaux à la racine du nombre à décomposer, on prend alors ces nombres dans l'ordre 1 par 1 et on teste, à chaque fois qu'on trouve un diviseur, on divise le nombre par ce diviseur et on continue l'opération avec le quotient. Il se peut que tout échoue, c'est tout simplement que le nombre était premier il est alors tout décomposé.

Café Python

Ce programme affiche la décomposition en facteurs premiers d'un nombre.