Par exemple, nous pouvons écrire que : 6 936 = 23 × 3 × 172 ou encore 1 200 = 24 × 3 × 52 et il n'existe aucune autre factorisation de 6 936 ou 1 200 sous forme de produits de nombres premiers, excepté par réarrangement des facteurs ci-dessus.
Le nombre 1 est le produit de zéro nombre premier (voir produit vide), de sorte que le théorème est aussi vrai pour 1.
Dans le livre VII de ses Éléments, Euclide énonce une proposition plus faible, suffisante pour certaines applications : tout nombre non premier est divisible par un nombre premier[1]. Mais dès son époque, la décomposition d'un nombre en facteurs premiers est connue et utilisée couramment[2]. Si le théorème n'est pas énoncé dans toute sa généralité c'est essentiellement parce que le formalisme de l'époque, dépourvu entre autres des puissances, ne permettait pas de l'exprimer simplement[3].
Supposons que tout entier strictement inférieur à un certain entier n > 1 est produit de nombres premiers. Soit p le plus petit entier strictement supérieur à 1 divisant n. Alors p est un nombre premier (tout entier naturel divisant p divise n, donc vaut p ou 1 par minimalité de p). On écrit alors n = pn/p avec n/p < n. L'hypothèse de récurrence implique que l'entier n/p s'écrit comme produit de nombres premiers, ce qui fournit une décomposition de n en produit de nombres premiers.
Par application du principe de récurrence, tous les entiers naturels peuvent s'écrire comme produits de nombres premiers.
Grâce au choix ci-dessus d'un « plus petit p » (au lieu, si n n'est pas premier, d'une décomposition quelconque[5]n = ab avec 1 < a, b < n), cette preuve explicite un algorithme (peu efficace cependant) de décomposition d'un entier naturel en produit de nombres premiers.
Unicité
La preuve de l'unicité[6] peut être obtenue à partir du lemme d'Euclide selon lequel, si un nombre premier p divise un produit ab, alors il divise a ou il divise b. Maintenant, prenons deux produits de nombres premiers qui sont égaux. Prenons n'importe quel nombre premier p du premier produit. Il divise le premier produit, et, de là, aussi le second. Par ce qui précède, p doit alors diviser au moins un facteur dans le second produit. Mais les facteurs sont tous des nombres premiers eux-mêmes, donc p doit être égal à un des facteurs du second produit. Nous pouvons donc simplifier par p les deux produits. En continuant de cette manière, nous voyons que les facteurs premiers des deux produits coïncident précisément.
Applications
Le théorème fondamental de l'arithmétique est lié au fait que tout entier naturel supérieur ou égal à 2 admet un facteur premier (voir la preuve de l'existence de la décomposition en facteurs premiers). Euclide utilisa ce résultat pour démontrer que les nombres premiers sont en quantité inépuisable : pour une famille finie de nombres premiers p1, p2, … , pn, le plus petit diviseur supérieur ou égal à 2 de l'entier 1+ p1p2…pn est un nombre premier qui n'est pas dans la famille initiale. En conséquence, aucune famille finie ne contient tous les nombres premiers (cf. « Théorème d'Euclide sur les nombres premiers »).
Le théorème fondamental intervient explicitement dans l'étude des fonctions additives et multiplicatives. En particulier, toute fonction complètement multiplicative est uniquement déterminée par les valeurs prises en les entiers premiers.
