Découvrir les nombres premiers

.
.

.
.

premiers
. . . . .

.

.
.

.
.

.
.

.
.

.
.
.
.
.

6
6
6

.
.
.
.
.

.
.
.
.
.

.
.

.
.

Divisibilité et nombres premiers
2.1 Théorème de Gauss et nombres
2.2 Conséquences. . . . . . . . . .

.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.

.
.

.
.

.
.

Décomposition, diviseurs d’un entier
3.1 Théorème fondamental de l’arithmétique
3.2 Diviseurs d’un entier. . . . . . . . . . . .
3.3 Problèmes. . . . . . . . . . . . . . . . . .

3

.
.

.
.

res

premiers

nomb

S

SPÉ

TERMINALE

Les

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

6
6
7
8

1

4

janvier

2013

MILAN

22

PAUL

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

. .
. .

.

exemple
. . . . .

Petit théorème de Fermat
4.1 Théorème, remarque et
4.2 Nombre de Poulet. . .

2

Table

des

matières

Définition et propriétés immédiates
1.1 Définition. . . . . . . . . . . .
1.2 Critère d’arrêt. . . . . . . . . .
1.3 Infinité des nombres premiers.
1.4 Crible d’Eratosthène. . . . . .
1.5 Nombres de Mersennes. . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.

.
.

10
10
11

1

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

2
2
2
3
3
5

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

2

1

1.1

1

DÉFINITION ET PROPRIÉTÉS IMMÉDIATES

Définition et propriétés immédiates

Définition

Définition 1 :Un nombre premier est un entier naturel qui admet exacte-
ment deux diviseurs : 1 et lui-même

Conséquence:
•1 n’est pas un nombre premier (il n’a qu’un seul diviseur)
•Un nombre premierpest un naturel supérieur ou égal à 2 soit :p>2.
•nombres premiers inférieurs à 100 sont :Les
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 et
97

1.2

Critère d’arrêt

Théorème 1 :Tout entier natureln,n>2, admet un diviseur premier.
Sinn’est pas premier, alors il admet un diviseur premierptel que :
26p6√n

Démonstration :
•Sinest premier, il admet donc un diviseur premier : lui-même.
•Sinn’est pas premier, l’ensemble des diviseursddentel que :

26d<n

n’est pas vide. Il admet donc un plus petit élémentp. Sipn’était pas premier, il
admettrait un diviseurd′tel que 26d′<pqui diviseraitn. Ceci est impossible
carpest le plus petit. Doncpest premier.
•On a doncppremier etn=p×qavecp6q. En multipliant cette inégalité par
p, on obtient :26pq⇔p26nsoitp6√n
p

Exemple 1 :Montrer que 109 est un nombre premier.
On a 10<√109<11.
On teste tous les nombres premiers strictement inférieurs à 11, soit :
2, 3, 5 et 7.
Des règles de divisibilté, on déduit que 109 n’est divible ni par 2, ni par 3, ni par
5.
En effectuant la division euclidienne de 109 par 7, on obtient :

109=7×15+4

109 n’est donc pas divisible par 7

Conclusion : comme 109 n’est pas divisible par 2, 3, 5, et 7, 109 est premier.

PAUL MILAN

22 janvier 2013

TERMINALESSPÉ

1.3

INFINITÉ DES NOMBRES PREMIERS

Algorithme :Un petit programme
pour déterminer si un nombreNest
premier. N’ayant pas à notre disposi-
tion la liste des nombres premiers, on
teste siNest divisible par 2, puis on
teste les diviseurs impairs par ordre
croissant tant que ceux-ci sont inférieur
à√N.

On obtient alors :
•527 est divisible par 17
•719 est premier
•11 111 est divisible par 41
•37 589 est premier

1.3 Infinité des nombres premiers

Variables
N,I
Initialisation
LireN
2→I
Traitement
SiEIN=IN
AfficherN, " est divisible par :" ,I
Stop
FinSi
I+1→I
Tant queI6√N
SiEIN=IN
AfficherN, " est divisible par :" ,I
Stop
FinSi
I+2→I
FinTantque
Sortie
AfficherN, est premier"
"

Théorème 2 :Il existe une infinité de nombres premiers

3

Démonstration :Supposons qu’il existe un nombre fini de nombres premiers :
p1,p2,. . .,pi, . . .,pn.
PosonsN=p1×p2×    ×pi×    ×pn+1
Nadmet un diviseur premier. Soitpice diviseur premier.
pidivisep1×p2×    ×pi×    ×pnetN.
Il divise donc la différenceN−(p1×p2×    ×pi×    ×pn) =1.
Ceci est impossible, donc l’hypothèse qu’il existe un nombre fini de nombres pre-
miers est absurde.

1.4 Crible d’Eratosthène

Pour dresser la liste des nombres premiers entre 2 et 150, la méthode du crible
d’Ératosthène consiste à :
•liste des nombres entiers inférieurs ou égal à 150 ;écrire la
•éliminer successivement les multiples propres1 puis ceux dede 2, de 3. . .p, où
pest le premier nombre non encore éliminé, etc
Les entiers éliminés (sur fond bleu dans le tableau ci après) sont les entiers non
premiers entre 2 et 150. Les entiers restant (sur fond jaune) sont donc les nombres
premiers inférieur à 150.
Remarque :
1. Pour éliminer les multiples propre de 7, commencer à 72, car les multiples
inférieurs ont déjà été éliminés.

1. multiple propre den: multiple dendistinct den

PAUL MILAN

22 janvier 2013

TERMINALESSPÉ

4

1 DÉFINITION ET PROPRIÉTÉS IMMÉDIATES

2. Il est possible de savoir à l’avance « jusqu’où aller ». En effet grâce au critère
d’arrêt, tout entier composénadmet un diviseur premierptel que :
26p6√n
Sin6150, alors√n6√150, or 12<√150<13 et donc tout entier non
premier sera éliminés en tant que multiple propre de 2, 3, 5, 7 et 11.

11
21
31
41
51
61
71
81
91

101
111
121
131
141

2
12
22
32
42
52
62
72
82
92
102
112
122
132
142

3
13
23
33
43
53
63
73
83
93

103
113
123
133
143

4
14
24
34
44
54
64
74
84
94

104
114
124
134
144

5
15
25
35
45
55
65
75
85
95
105
115
125
135
145

6
16
26
36
46
56
66
76
86
96
106
116
126
136
146

7
17
27
37

47
57
67
77
87
97
107
117
127
137
147

8
18
28
38
48
58
68
78
88
98
108
118
128
138
148

9
19
29
39
49
59
69
79
89
99
109
119
129
139
149

10
20
30
40
50
60
70
80
90
100
110
120
130
140
150

On peut écrire l’algorithme suivant et sa traduction avec Algobox :

PAUL MILAN

Variables
N,I,A,M,P,L1(liste),L2(liste)
Initialisation
LireN
Pour I de 2 àN*
I→L1(I)
FinPour
2→A
0→P
Traitement
Tant queA6N
Tant queL1(A) =0
A+1→A
FinTantque
SiA6N
P+1→P
L1(A)(→L2(P)
ENA→Q
FinSi
Pour I de 1 àQ
A∗I→M
0→L1(M)
FinPour
FinTantque
So