Théorème fondamental de l'arithmétique

(i) Le pgcd $p \wedge a$ divise $p$, donc vaut $1$ ou $p$. S'il vaut $p$, alors $p \mid a$. Sinon $p \wedge a = 1$, et le lemme de Gauss donne $p \mid b$ (PGCD, Bézout).

(ii) Existence. Sinon, soit $n$ le plus petit entier $\geqslant 2$ qui ne soit pas un produit de nombres premiers (Bon ordre sur ℕ). Il n'est pas premier : il a un diviseur $a \in \mathbb N$ autre que $1$ et $n$, et $n = ab$ avec $b \in {\mathbb Z}$. On a $a \neq 0$, puisque $n \neq 0$, puis $b > 0$, sans quoi $ab \leqslant 0$ (Ordre de ℤ), et $b \neq 1$, puisque $a \neq n$. Donc $a, b \geqslant 2$, d'où $n = ab \geqslant 2b > b$ et $n \geqslant 2a > a$. Par minimalité, $a$ et $b$ sont des produits de nombres premiers, donc $n$ aussi : contradiction.

Unicité. Supposons $p_1 \cdots p_k = q_1 \cdots q_l$, produits de nombres premiers, et raisonnons par récurrence sur $k$. Si $k = 0$, le membre de gauche vaut $1$, et le membre de droite aussi, ce qui impose $l = 0$, tout produit d'au moins un nombre premier étant $\geqslant 2$.

Si $k \geqslant 1$, le membre de gauche est $\geqslant 2$, donc $l \geqslant 1$. Par (i), étendu à un produit quelconque par récurrence sur le nombre de facteurs, $p_1$ divise l'un des $q_j$ ; comme $q_j$ est premier et $p_1 \geqslant 2$, $p_1 = q_j$.

On simplifie par $p_1 = q_j$, ce que permet l'intégrité de ${\mathbb Z}$ (Anneau ℤ) : il reste $k - 1$ facteurs à gauche et $l - 1$ à droite, et l'on conclut par l'hypothèse de récurrence : les deux décompositions comportent les mêmes facteurs, avec les mêmes multiplicités.

(iii) Soit $p$ un nombre premier et $N$ le produit de tous les nombres premiers inférieurs ou égaux à $p$, plus $1$. Un facteur premier $q$ de $N$, qui existe par (ii), ne divise pas $N - 1$, sinon il diviserait $1$ ; donc $q$ n'est aucun des nombres premiers $\leqslant p$, et $q > p$.