Récurrence forte. Montrer que tout entier n ≥ 2 admet un diviseur…

Ce qu'il faut démontrer. Tout entier $n\ge 2$ admet au moins un diviseur premier.

Démonstration par récurrence forte. Notons $P(n)$ l'assertion « $n$ admet un diviseur premier », pour $n\ge 2$.

Initialisation. $P(2)$ est vraie : $2$ est premier et $2\mid 2$.

Hérédité (forme forte). Soit $n\ge 2$. Supposons $P(k)$ vraie pour tout entier $k$ tel que $2\le k<n$, et montrons $P(n)$. Deux cas :

• $n$ est premier. Alors $n$ est lui-même un diviseur premier de $n$, et $P(n)$ est vraie.
• $n$ n'est pas premier. Comme $n\ge 2$, il admet un diviseur $a$ autre que $1$ et $n$ ; écrivons $n=ab$ avec $$2\le a<n$$ L'hypothèse de récurrence s'applique à $a$ : il existe un nombre premier $p$ tel que $p\mid a$. Comme $a\mid n$, la transitivité de la divisibilité donne $p\mid n$, et $P(n)$ est vraie.

Dans les deux cas $P(n)$ est établie ; par récurrence forte, $P(n)$ est vraie pour tout $n\ge 2$. $■$

Pourquoi la forme forte est indispensable. Une récurrence simple ne mettrait à disposition que $P(n-1)$. Or l'hypothèse est appliquée ici à un diviseur $a$ de $n$, dont rien ne dit qu'il vaut $n-1$ : pour $n=12$, on peut tomber sur $a=3$, et $P(11)$ ne sert à rien. C'est la structure du problème — on descend vers un diviseur, pas vers le prédécesseur — qui impose la forme forte.

Retenir la silhouette de cette preuve : c'est le premier étage du théorème fondamental de l'arithmétique, dont la décomposition en facteurs premiers s'obtient en itérant l'argument.