Chargement de l'audio en cours
Plus

Plus

1. L’ensemble des nombres premiers
P.148-149

Mode édition
Ajouter

Ajouter

Terminer

Terminer

COURS 1


1
L’ensemble des nombres premiers




A
Définition


Définition

Un entier naturel est un nombre premier s’il admet exactement deux diviseurs positifs : 11 et lui‑même.

Remarques

11 n’est pas un nombre premier car il n’admet qu’un seul diviseur positif : lui‑même. 00 n’est pas non plus un nombre premier car il admet une infinité de diviseurs.

Exemple

La liste des nombres premiers inférieurs à 100100 est la suivante : 22 ; 33 ; 55 ; 77 ; 1111 ; 1313 ; 1717 ; 1919 ; 2323 ; 2929 ; 3131 ; 3737 ; 4141 ; 4343 ; 4747 ; 5353 ; 5959 ; 6161 ; 6767 ; 7171 ; 7373 ; 7979 ; 8383 ; 8989 ; 9797.

B
Test de primalité


Propriété

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

DÉMONSTRATION

Soit nn un entier supérieur ou égal à 22.
On note Pn\mathrm{P}_n la proposition : « Tout entier naturel compris entre 22 et nn admet un diviseur premier. »

Initialisation : Pour n=2n=2
22 est divisible par 22 qui est premier donc on en déduit que P2\mathrm{P}_2 est vraie.

Hérédité : On considère un entier naturel k2k \geqslant 2 tel que Pk\mathrm{P}_k est vraie (hypothèse de récurrence). On souhaite démontrer que Pk+1\mathrm{P}_{k+1} est vraie.
Puisque Pk\mathrm{P}_k est vraie, tous les entiers naturels compris entre 2\text{2} et kk admettent un diviseur premier. Il suffit donc de montrer que k+1k+1 admet un diviseur premier.
  • Si k+1k+1 est premier, il admet alors un diviseur premier : lui‑même.
  • Sinon, il existe deux entiers aa et bb compris entre 22 et kk tels que k+1=abk+1 = ab.

aa étant un entier naturel inférieur ou égal à kk, l’hypothèse de récurrence donne l’existence d’un diviseur premier de aa noté pp.
D’où pap | a et a(k+1)a |(k+1) donc p(k+1)p |(k+1) et ainsi Pk+1\mathrm{P}_{k+1} est vraie.
Ainsi, P2\mathrm{P}_2 est vraie et, pour tout entier k2k \geqslant 2, si Pk\mathrm{P}_k est vraie, alors Pk+1\mathrm{P}_{k+1} est vraie aussi.
D’après le principe de récurrence, on en déduit que, pour tout entier n2n \geqslant 2, Pn\mathrm{P}_n est vraie donc que tout entier naturel supérieur ou égal à 22 est divisible par un nombre premier.

Remarque

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

Propriété

Tout entier n2n \geqslant 2 qui n’est pas premier admet un diviseur premier pp compris entre 22 et n\sqrt{n}.

Remarque

On peut donc tester la primalité d’un entier nn en étudiant sa divisibilité par les nombres premiers compris entre 22 et n\sqrt n.

DÉMONSTRATION

Voir exercice 
42
p. 157
.

Application et méthode - 1

Énoncé

Montrer que l’entier 5353 est premier.

Méthode

Pour démontrer qu’un entier nn est un nombre premier :
  • on dresse la liste de tous les nombres premiers inférieurs ou égaux à n\sqrt n ;
  • on vérifie qu’aucun de ces nombres ne divise nn, en montrant par exemple que le reste de la division euclidienne de nn par ces nombres n’est pas nul.

Solution


Supposons par l’absurde que 5353 n’est pas premier.
D’après les propriétés précédentes, il existe alors un diviseur premier de 5353 inférieur à 53\sqrt{53}. Comme 7<53<87 \lt \sqrt{53} \lt 8, on doit tester tous les nombres premiers strictement inférieurs à 88, à savoir 22 ; 33 ; 55 et 77.
  • D’après les critères de divisibilité, il est clair que 5353 n’est ni divisible par 22, ni par 33, ni par 55.
  • 77 ne divise pas 5353 car le reste de la division euclidienne de 5353 par 77 est 44.

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

Pour s'entraîner : exercices 23, 24 et 25 p. 156

C
Une infinité de nombres premiers


Propriété

Il existe une infinité de nombres premiers.

DÉMONSTRATION

Voir activité 
B
p. 146
.

Exemple

On peut démontrer, en utilisant un raisonnement similaire, qu’il existe également une infinité de nombres premiers de la forme 4n+34n + 3 (voir exercice
51
p. 158
).
Par exemple, 3=4×0+33=4 \times 0+3, 7=4×1+37=4 \times 1+3 et 11=4×2+311=4 \times 2+3 sont premiers.
Certains nombres premiers, cependant, ne peuvent pas s’écrire sous cette forme. C’est notamment le cas de 22 ou de 55. De même, tout nombre s’écrivant sous la forme 4n+34n + 3 n’est pas nécessairement premier. C’est notamment le cas de 15=4×3+315=4 \times 3+3.
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.