Décomposition d'un nombre entier en produit de nombres premiers

Dans cette fiche, nous allons nous intéresser à la décomposition d’un nombre entier naturel en produit de nombres premiers.

Afin de démontrer cet algorithme nous avons besoin de la propriété suivante :

Un nombre entier naturel strictement supérieur à $1$ est premier ou se décompose de manière unique, à l’ordre près, en produit de nombres premiers.

$n$ est un entier naturel non premier. Il admet alors un diviseur strict premier $p_1$. Donc $n=p_1\times q_1$ où $q_1$ est aussi un diviseur strict de $n$ (sinon $p_1=1$ ou $p_1=n$, ce qui est impossible). Ainsi $q_1$ est strictement inférieur à l’entier $n$.

• Si $q_1$ est premier, alors $n$ est le produit de deux nombres premiers : $n=p_1\times q_1$
• Si $q_1$ n’est pas premier, alors il admet un diviseur strict premier $p_2$. Donc $q_1=p_2\times q_2$ où $p_2$ est un diviseur strict de $q_1$. Ainsi $q_2 < q_1 < n$.
• Si $p_2$ est premier, $n$ est le produit de trois nombres premiers $n=p_1\times p_2\times q_2$

Tant que $q_i$ n’est pas premier, on réitère ce processus. On construit ainsi une suite d’entiers naturels $1 ≤ q_i < q_{i-1} < … < q_3 < q_2 < q_1$.

Comme cette suite est finie, ce processus doit s’arrêter : il existe donc un diviseur $q_k$ premier.

Ainsi, $n$ est le produit de facteurs premiers $n=p_1\times p_2\times …\times p_k\times q_k$.

L’unicité de la décomposition est admise.