Tout entier naturel supérieur ou égal à $2$ est divisible par un nombre premier.

Soit $n$ un entier supérieur ou égal à $2$.
On note ${\mathrm{P}}_n$ 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 ${\mathrm{P}}_2$ est vraie.

Hérédité : On considère un entier naturel $k⩾2$ tel que ${\mathrm{P}}_k$ est vraie (hypothèse de récurrence). On souhaite démontrer que ${\mathrm{P}}_{k+1}$ est vraie.
Puisque ${\mathrm{P}}_k$ est vraie, tous les entiers naturels compris entre $\text{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 ${\mathrm{P}}_{k+1}$ est vraie.
Ainsi, ${\mathrm{P}}_2$ est vraie et, pour tout entier $k⩾2$, si ${\mathrm{P}}_k$ est vraie, alors ${\mathrm{P}}_{k+1}$ est vraie aussi.
D'après le principe de récurrence, on en déduit que, pour tout entier $n⩾2$, ${\mathrm{P}}_n$ est vraie donc que tout entier naturel supérieur ou égal à $2$ est divisible par un nombre premier.

La propriété ${\mathrm{P}}_n$ est un peu particulière ici : elle concerne tout entier inférieur ou égal à $n$ et pas seulement l'entier $n$. On dit qu'il s'agit d'une propriété de récurrence forte.

Supposons par l'absurde que $53$ n'est pas premier.
D'après les propriétés précédentes, il existe alors un diviseur premier de $53$ inférieur à $\sqrt{53}$. Comme $7<\sqrt{53}<8$, on doit tester tous les nombres premiers strictement inférieurs à $8$, à savoir $2$ ; $3$ ; $5$ et $7$.

• D'après les critères de divisibilité, il est clair que $53$ n'est ni divisible par $2$, ni par $3$, ni par $5$.
• $7$ ne divise pas $53$ car le reste de la division euclidienne de $53$ par $7$ est $4$.

Finalement, aucun de ces nombres ne divise $53$, donc $53$ est premier.

Exercices

23

,

24

et

25

p. 156

Il existe une infinité de nombres premiers.

Voir activité 

B

p. 146.

On peut démontrer, en utilisant un raisonnement similaire, qu'il existe également une infinité de nombres premiers de la forme $4n+3$ (voir exercice

51

p. 158).
Par exemple, $3=4\times 0+3$, $7=4\times 1+3$ et $11=4\times 2+3$ sont premiers.
Certains nombres premiers, cependant, ne peuvent pas s'écrire sous cette forme. C'est notamment le cas de $2$ ou de $5$. De même, tout nombre s'écrivant sous la forme $4n+3$ n'est pas nécessairement premier. C'est notamment le cas de $15=4\times 3+3$.