Un nombre premier est un entier naturel supérieur à 1 qui n’a que deux diviseurs : 1 et lui-même (par exemple 2, 3, 5, 7, 11…).
Un entier naturel supérieur à 1 qui n’est pas premier est dit composé. Il peut être « cassé » en un produit de facteurs plus petits (par exemple $12 = 2 \times 6$ ou $12 = 3 \times 4$).
Le théorème fondamental de l’arithmétique affirme que ce processus de décomposition s’arrête lorsque tous les facteurs sont des nombres premiers, et que le résultat final est toujours le même, quel que soit le chemin de décomposition choisi.
Tout entier $n \ge 2$ se décompose en un produit de nombres premiers. De plus, cette décomposition est unique à l’ordre près des facteurs.
Formellement, pour tout entier $n \ge 2$, il existe une unique suite de nombres premiers $p_1 \le p_2 \le \dots \le p_k$ et une unique suite d’exposants entiers $\alpha_1, \dots, \alpha_k \ge 1$ telles que : $$ n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k} $$
Démonstration Détaillée
La démonstration se fait en deux parties : l’existence de la décomposition et son unicité.
Partie 1 : Existence de la Décomposition
On utilise un raisonnement par récurrence forte sur l’entier $n \ge 2$.
- Base (n=2) : L’entier 2 est un nombre premier, il est donc son propre produit de nombres premiers. La propriété est vraie.
-
Hérédité : Supposons que la propriété est vraie pour tous les entiers $k$ tels que $2 \le k < n$. Montrons qu'elle est vraie pour $n$.
- Si $n$ est un nombre premier, alors il est son propre produit de nombres premiers, et la propriété est vérifiée.
- Si $n$ est un nombre composé, il peut s’écrire comme un produit $n = a \times b$, où $a$ et $b$ sont des entiers tels que $1 < a < n$ et $1 < b < n$. Par l'hypothèse de récurrence, $a$ et $b$ peuvent tous deux être décomposés en produits de nombres premiers. Le produit de ces deux décompositions donne alors une décomposition de $n$ en produit de nombres premiers.
Par le principe de récurrence forte, tout entier $n \ge 2$ admet une décomposition en produit de facteurs premiers.
Partie 2 : Unicité de la Décomposition
Cette partie repose sur le lemme d’Euclide : si un nombre premier $p$ divise un produit $ab$, alors $p$ doit diviser $a$ ou $p$ doit diviser $b$.
On raisonne par l’absurde. Supposons qu’il existe un entier $n$ qui admet deux décompositions distinctes en facteurs premiers : $$ n = p_1 p_2 \dots p_r = q_1 q_2 \dots q_s $$ où les $p_i$ et les $q_j$ sont des nombres premiers, ordonnés par taille croissante.
- Puisque $p_1$ divise le produit $q_1 q_2 \dots q_s$, d’après le lemme d’Euclide (généralisé), $p_1$ doit diviser l’un des $q_j$. Comme les $q_j$ sont premiers, $p_1$ doit être égal à l’un d’eux.
- De même, $q_1$ doit être égal à l’un des $p_i$.
- Puisque les listes sont ordonnées, on a $p_1 \le p_i$ et $q_1 \le q_j$ pour tous $i,j$. La seule possibilité est que $p_1 = q_1$.
- On peut alors simplifier l’égalité par $p_1$ : $$ p_2 \dots p_r = q_2 \dots q_s $$
- On peut répéter ce processus, en montrant que $p_2=q_2$, $p_3=q_3$, etc., jusqu’à épuiser l’une des listes de facteurs. Si les listes n’avaient pas la même longueur (par exemple $r < s$), on arriverait à une égalité de la forme $1 = q_{r+1} \dots q_s$, ce qui est impossible car les $q_j$ sont des nombres premiers (donc $>1$).
Les deux listes de facteurs premiers doivent donc être identiques. La décomposition est unique à l’ordre près des facteurs.
Implications et Utilisation
- Fondement de l’Arithmétique : Ce théorème est la raison pour laquelle on l’appelle « fondamental ». Il garantit que la structure multiplicative des entiers est bien définie et unique.
- Calcul du PGCD et du PPCM : La décomposition en facteurs premiers est la méthode la plus directe pour calculer le Plus Grand Commun Diviseur (PGCD) et le Plus Petit Commun Multiple (PPCM) de deux nombres.
- Cryptographie : La sécurité de nombreux systèmes cryptographiques, notamment RSA, repose sur le fait qu’il est très facile de multiplier de grands nombres premiers, mais extrêmement difficile de faire l’opération inverse : trouver la décomposition en facteurs premiers d’un très grand nombre.