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$1p1​. Donc $n=p$1\times q1 où $q$1 est aussi un diviseur strict de $n$ (sinon $p$1=1p1​=1 ou $p$1=n, ce qui est impossible). Ainsi $q_1$ est strictement inférieur à l’entier $n$.

• Si $q$1q1​ est premier, alors $n$ est le produit de deux nombres premiers : $n=p$1\times q_1
• Si $q$1q1​ n’est pas premier, alors il admet un diviseur strict premier $p$2. Donc $q$1=p2\times q2q1​=p2​×q2​ où $p$2 est un diviseur strict de $q$1q1​. Ainsi $q$2 < q_1 < n.
• Si $p$2p2​ est premier, $n$ est le produit de trois nombres premiers $n=p$1\times p2\times q2

Tant que $q$iqi​ n’est pas premier, on réitère ce processus. On construit ainsi une suite d’entiers naturels $1 ≤ q$i < q{i-1} < … < q3 < q2 < q1.

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 p2\times …\times pk\times qk.

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