Médaille
N°1 pour apprendre & réviser du collège au lycée.
Décomposition d'un nombre entier en produit de nombres premiers
Démonstration

Introduction

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

Prérequis

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

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

Démonstration

nn est un entier naturel non premier. Il admet alors un diviseur strict premier p1p1. Donc n=p1×q1n=p1\times q1q1q1 est aussi un diviseur strict de nn (sinon p1=1p1=1 ou p1=np1=n, ce qui est impossible). Ainsi q1q_1 est strictement inférieur à l’entier nn.

  • Si q1q1 est premier, alors nn est le produit de deux nombres premiers : n=p1×q1n=p1\times q_1
  • Si q1q1 n’est pas premier, alors il admet un diviseur strict premier p2p2. Donc q1=p2×q2q1=p2\times q2p2p2 est un diviseur strict de q1q1. Ainsi q2<q1<nq2 < q_1 < n.
  • Si p2p2 est premier, nn est le produit de trois nombres premiers n=p1×p2×q2n=p1\times p2\times q2

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

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

Ainsi, nn est le produit de facteurs premiers n=p1×p2××pk×qkn=p1\times p2\times …\times pk\times qk.

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