Existence d'un diviseur premier : énoncé (MPSI)

Soit $n \geqslant 2$.

1. Le plus petit diviseur $p \geqslant 2$ de $n$ est un nombre premier. En particulier, $n$ admet au moins un diviseur premier.
2. Si $n$ est composé, ce plus petit diviseur vérifie $p \leqslant \sqrt{n}$.

Preuve. L'ensemble des diviseurs $d \geqslant 2$ de $n$ contient $n$, il admet un plus petit élément $p$. Si $p$ n'était pas premier, il aurait un diviseur $d$ avec $1 < d < p$ ; alors $d \mid n$, ce qui contredit la minimalité de $p$.

Si $n$ est composé, $n = pm$ avec $m \geqslant 2$ ; $m$ est un diviseur de $n$ supérieur ou égal à $2$, donc $m \geqslant p$. Ainsi $n = pm \geqslant p^2$, soit $p \leqslant \sqrt{n}$.