Tout entier a un diviseur premier

Démonstration rédigée par Manuel, un prof particulier de maths passionné et expérimenté, qui pourra vous aider à faire face à la MPSI.

Nombre premier. Un nombre premier $p$ est un nombre entier naturel, supérieur ou égal à 2, seulement divisible par 1 et par lui-même.

Proposition. Tout nombre entier $n\ge 2$ admet un diviseur premier.

Démonstration 1 (récurrence forte)

On cherche à démontrer, pour tout $n\ge 2$ , la propriété $P_n$: "$n$ admet un diviseur premier".

Initialisation.

2 est un nombre premier, donc admet bien un diviseur premier : lui même.

Hérédité.

Soit un entier $n\ge 2$ tel que, pour tout $k\in [[2,n]]$, $P_k$ est vraie. Montrons $P_{n+1}$; c'est à dire que $n+1$ admet un diviseur premier.

Si $n+1$ est un nombre premier, alors il admet un diviseur premier : lui même.

Si $n+1$ n'est pas premier, alors il admet un diviseur strict $m\in [[2,n]]$. Par hypothèse de récurrence, $m$ admet un diviseur premier $p$. Mais comme $m$ divise $n+1$ et $p$ divise $m$, $p$ divise aussi $n+1$, en plus d'être premier.

$n+1$ admet donc bien un diviseur premier.

Conclusion.

La propriété $P_n$ est vraie au rang $n=2$ et est héréditaire, elle est donc vraie pour tout entier naturel $n\ge 2$. On a bien montré que tout entier plus grand que $2$ admet un diviseur premier.

Démonstration 2 (ensembliste)

Soit $n\ge 2$.

Cas où $n$ est premier. Il admet donc bien un diviseur premier: lui-même.

Cas où $n$ n'est pas premier. S'il n'est pas premier, alors l'ensemble $A_n$ des diviseurs de $n$ différents de 1 et $n$ est non vide. $A_n$ étant un sous-ensemble non vide de $\mathbb{N}$, il admet donc un plus petit élément $p$. Montrons que $p$ est premier.

Supposons qu'il existe un diviseur $d$ de $p$ différent de $1$ et de $p$. $d$ est alors un diviseur de $n$ différent de $1$ et de $n$, donc $d\in A_n$ et $d<p$. Mais c'est impossible par construction de $p$, donc $p$ n'a que $1$ et $p$ pour diviseurs.

Comme $p$ est supérieur à 2 par construction, $p$ est donc premier. De plus, $p$ divise $n$.

Ainsi, tout entier a un diviseur premier.