Soit
n un entier supérieur ou égal à
2.
On note
Pn la proposition : « Tout entier naturel compris entre
2 et
n admet un diviseur premier. »
Initialisation : Pour
n=2
2 est divisible par
2 qui est premier donc on en déduit que
P2 est vraie.
Hérédité : On considère un entier naturel
k⩾2 tel que
Pk est vraie (hypothèse de récurrence). On souhaite démontrer que
Pk+1 est vraie.
Puisque
Pk est vraie, tous les entiers naturels compris entre
2 et
k admettent un diviseur premier. Il suffit donc de montrer que
k+1 admet un diviseur premier.
- Si k+1 est premier, il admet alors un diviseur premier : lui‑même.
- Sinon, il existe deux entiers a et b compris entre 2 et k tels que k+1=ab.
a étant un entier naturel inférieur ou égal à
k, l'hypothèse de récurrence donne l'existence d'un diviseur premier de
a noté
p.
D'où
p∣a et
a∣(k+1) donc
p∣(k+1) et ainsi
Pk+1 est vraie.
Ainsi,
P2 est vraie et, pour tout entier
k⩾2, si
Pk est vraie, alors
Pk+1 est vraie aussi.
D'après le principe de récurrence, on en déduit que, pour tout entier
n⩾2,
Pn est vraie donc que tout entier naturel supérieur ou égal à
2 est divisible par un nombre premier.