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 \geqslant 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 \geqslant 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 \geqslant 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 \lt \sqrt{53} \lt 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.