121 Nombres premiers.

Applications

CHADAD Omar
[email protected]
December 17, 2019

Rapport Jury 2019

Le sujet de cette leçon, souvent appréciée des candidats, est très vaste. Elle doit donc être abordée en faisant des
choix qui devront être clairement motivés. La répartition des nombres premiers doit être évoquée : certains résultats
sont accessibles dans le cadre du programme du concours, d’autres peuvent être admis et cités pour leur importance
culturelle. Des conjectures classiques ont aussi leur place dans cette leçon. On peut définir certaines fonctions importantes
en arithmétique, les relier aux nombres premiers et illustrer leurs utilisations. Il est particulièrement souhaitable de
s’intéresser aussi aux aspects algorithmiques du sujet (tests de primalité). En plus d’une étude purement interne à
l’arithmétique des entiers, il est important d’exhiber des applications dans différents domaines : théorie des corps finis,
théorie des groupes, arithmétique des polynômes, cryptographie, etc. La réduction modulo p n’est pas hors-sujet et
constitue un outil puissant pour résoudre des problèmes arithmétiques simples.

Références
[FGN]: Oraux X-ENS algèbre 1, S.Francinou, H.Gianella, S.Nicolas
[GOU]: les maths en tête algèbre, Xavier GOURDON

Plan
1 Généralités
1.1 Définitions et théorèmes
1. Nombre premiers dans Z, notation P
2. Nombres premiers entre eux, pgcd, ppcm
3. Théorèmes de Gauss:

• a ∧ b = 1 et a|bc ⇒ a|c
• a ∧ b = 1, a|c et b|c ⇒ ab|c
4. Propositions:
i) ∀p ∈ P, ∀n ∈ Z: si p - n alors p ∧ n = 1
ii) ∀n ≥ 2, ∃p ∈ P, p | n
iii) p ∈ P ⇐⇒ Z/pZ est un corps
5. Exemples:
i) Nombre de Fermat [FGN p: 132]:
n
• Fn = 22 + 1
• 2a + 1 est premier =⇒ ∃k ∈ N, a = 2k
• Fn est premier pour n ∈ {0, 1, 2, 3, 4} pas pour n = 5
• ∀p 6= q ∈ N : Fq ∧ Fp = 1

1
 ii) Nombre de Mersenne [GOU p:11]:
• Mp = 2p − 1 avec p premier
• ap − 1 premier =⇒ a = 2, p ∈ P
• M11 n’est pas premiers
• ∀p 6= q ∈ N : Mq ∧ Mp = 1

1.2 Recherche des nombres premiers:

1. Théorème de Fermat : ∀a ∈ Z, p ∈ P : ap ≡ a[p]
2. Théorème de Wilson [FGN p: 128] : p ∈ P ⇐⇒ (p − 1)! ≡ −1[p]
√
3. Crible d’Eratosthène : n ∈
/ P ⇐⇒ ∃p ∈ P avec p ≤ n et p | n

2 Factorisation en produit de nombres premiers

1. Théorème fondamental de l’arithmétique
2. Valuation p-adique:

• Définition: ∀n ∈ N, ∀p ∈ P : vp (n) = max k ∈ N/pk | n
• Formule de Legendre (Oraux X-ENS p 139):
+∞  
X n
vp (n!) =
pk
k=1

• application: Par combien de zéros se termine 2019!

3. Fonctions arithmétiques multiplicatives:

• Définition: f : N∗ 7−→ C vérifiant ∀m, n ∈ N : m ∧ n = 1 =⇒ f (mn) = f (m)f (n)

• Exemples de fonctions multiplicatives:
– Fonction indicatrice d’Euler:
ϕ : N∗ −→ N∗
n 7−→ ϕ (n) = card {p ∈ {1, .., n} /p ∧ n = 1}

– Fonction de Möbius µ :

µ : N∗ −→ {−1, 0, 1}

 1 si n = 1
n 7−→ µ (n) = 0 si n est divisible par le carée d’ un nombre premier
(−1)r si n = p1 p2 ...pr décomposition en nombres premiers



P 1 si n = 1
– On a µ(d) = [FGN p: 156]
d|n
0 ∀n ∈ N∗ \{1}

3 Répartition des nombres premiers

1. P est infini [GOU p: 9]
2. Proposition : Il existe un suite aussi longue que l’on souhaite sans nombres premiers (n! + i pour 2 ≤ i ≤ n)

2
 3. DEV1 [GOU p:43]: Postulat de Bertrand:
∀n ≥ 4, ∃p ∈ P : n ≤ p ≤ 2n − 2

4. DEV2 [FGN p: 156]: Probabilité que deux entiers de {1, .., n} soient premiers entre eux:
n h n i2
1 X 6
rn = 2
µ(d) −→ 2
n d n→+∞ π
d=1

4 Développement 1
Cette démonstration est due à Paul Erdös (1932).
Notation:
• ∀n ∈ N∗ : Pn = P ∩ {1, .., n}
• ∀n ∈ N∗ : π (n) = card (Pn )

4.1 Inégalités préliminaires

Y
• ∀n ≥ 2 : p < 4n :
p∈Pn
Y
Par récurrence simple sur n; pour 2 c’est vérifié, soit n ≥ 2 on suppose que p < 4n , si n est paire alors :
p∈Pn
∃k ∈ N : n = 2k donc Pn+1 = P2k+1 et on note Ak = P2k+1 \Pk
Or: Y Y Y Y Y
p= p= p p < 4k+1 p
p∈Pn+1 p∈P2k+1 p∈Pk+1 p∈Ak p∈Ak

k k
d’autre part ∀p ∈ Ak : p | (k + 1)!C2k+1 donc p | C2k+1 car p ∧ (k + 1)! = 1 ainsi:
Y Y
k k k k−1
p | C2k+1 alors p ≤ C2k+1 = C2k + C2k < 4k
p∈Ak p∈Ak

Y
finalement: p < 4k+1 4k = 42k+1 = 4n+1 . Si n est impaire alors ∃k ∈ N tel que n+1 = 2k +2 or P2k+2 = P2k+1
p∈Pn+1
Y Y
on déduit: p= p < 42k+1 < 4n+1 CQFD.
p∈Pn+1 p∈P2k+1

n
• ∀n ≥ 14 : π (n) ≤ − 1:
2 hni
Pour n = 14 c’est vérifié, sinon n ≥ 15 donc dans {1, 2, .., n} il ya − 1 nombres composées (paires sans compter
hni 2
2), ajoutons 1, 9, 15 ça fait au moins + 2 donc
2
hni n
π (n) ≤ n − +2≤ −1
2 2
n
4.2 Calcul de vp (C2n )
Soit n ≥ 2,p ∈ P par la formule de Legendre on a :
m    
n
X 2n n
vp (C2n ) = vp ((2n)!) − 2vp (n!) = −2 k
pk p
k=1
 
ln(2n) n ln(2n) n
Où m = , on déduit alors que vp (C2n )≤m≤ d’où pvp (C2n ) ≤ 2n en particulier si p | C2n
n
alors p ≤ 2n
ln(p) ln(p)
dans ce cas: m ≤ 1

3
 √
  

2n n
• Si p > 2n: alors pk > 2n > n, ∀k ≥ 2 donc : vp (C2n
n
)= −2 ∈ {0, 1}
p p
   
2 2n n 2n n n 4
• Si n ≥ 3 et n < p ≤ n: < 3 et ≥ 1 d’où −2 < 1 donc vp (C2n ) = 0 car p2 > n2 > n donc
  3 p p p p   9
n 2n
∀k ≥ 2 k = 0, d’autre par 9(p2 − 2n) ≥ 4n(n − 4) + 1 donc si n ≥ 4 alors p2 > 2n et ainsi = 0, ∀k ≥ 2, le
p   pk
2 2n
cas n = 3, on a 3 = n ≥ p > n = 2 alors p = 3 on vérifie que = 0, ∀k ≥ 2
3 pk
n
Conclusion : vp (C2n ) = 0
       
2n 1 n 2n n k 2n n
• Si n < p ≤ 2n: alors 1 ≤ < 2 et ≤ < 1 d’où −2 = 1 et ∀k ≥ 2, p > 2n > n alors k = k = 0
p 2 p p p p p
n
ainsi vp (C2n )=1
 √
 0 ou 1 Si p > 2n

n 2
• Conclusion: vp (C2n )= 0 Si n ≥ 3 et n < p ≤ n
 3
Si n < p ≤ 2n

1

4.3 preuve du postulat

n
On note ∀p ∈ P : rp = vp (C2n ) on peut écrire alors:
Y
n
C2n = prp
p∈P
Y2n Y Y
= prp × p× p
√ √
p≤ 2n 2n<p≤ 32 n p∈P2n \Pn
√
π ( 2n) 23 n
Y
≤ (2n) 4 p
p∈P2n \Pn

√
√ n 4n
Pour n ≥ 98 on a π 2n ≤ 2n − 1 et on peut montrer par récurrence simple sur n ∈ N que C2n > √ donc:
2 n
n
Y 43
(2n)π(2n)−π(n) > p> √ √ n (?)
p∈P2n \Pn 2 n(2n) 2
√ n n √
Si n ≥ 450 on peut montrer que :(2n) n/2 ≤ 2 3 et 2 3 > 4n n et donc:
n
43
√ √ n > 2n(??)
2 n(2n) 2
De (?) et (??) on déduit que ∀n ≥ 450 : π(2n) − π(n) > 1 pour 4 ≤ n ≤ 450 une vérification manuelle permet de
confirmer le résultat

5 Développement 2
Soit n ∈ N\{0, 1} montrons que la probabilité pour que deux nombres de {1, .., n} soient premiers entre eux est:
n h n i2
1 X
rn = 2
µ(d)
n d
d=1

On note An = {(a, b) ∈ {1, .., n}2 /a ∧ b = 1}, alors {1, .., n}2 = An ∪ Acn , ainsi
card(An ) n2 − card(Acn )
rn = 2
=
n n2

4
Soit p1 , p2 , ..., pk les nombres premiers inférieurs à n, alors ∀(a, b) ∈ {1, .., n}2 :

(a, b) ∈ Acn ⇐⇒ a ∧ b 6= 1
⇐⇒ ∃j ∈ {1, .., k} pj | a et pj | b
k 
Donc Acn = Pi où: Pi = (a, b) ∈ {1, .., n}2 /pi | a et pi | b pour i ∈ {1, .., k}
S
i=1
En utilisant la formule de Crible:
k
! !
[ X \
card(Acn ) = card Pi = (−1) card(I)+1
card Pi (?)
i=1 ∅6=I⊂{1,..,k} i∈I

Soit H ⊂ {1, .., k} et H 6= ∅, alors ∀ (a, b) ∈ {1, .., n}2 :

T
(a, b) ∈ Pi ⇐⇒ ∀i ∈ H: (a, b) ∈ Pi
i∈H
⇐⇒ ∀i
Q∈ H: pi | aQ
et pi | b
⇐⇒ pi | a et pi | b
i∈H i∈H
pi dans {1, ..., n}}2
Q
⇐⇒ (a, b) ∈ { multiples de
i∈H

 2
   2
T Q n
On en déduit: card Pi = card { multiples de pi dans {1, ..., n}} =  Q 
i∈H i∈H pi
i∈H
On remplace dans (?):
2
X n
card(Acn ) = (−1)card(I)+1  Q  (??)
pi
∅6=I⊂{1,..,k} i∈I

pi et dans ce cas µ(d) = (−1)card(J) , soit µ(d) = 0

Q
Or ∀d ∈ {2, ..., n}:Soit ∃J ⊂ {1, .., k} tel que: d =
i∈J
Donc (??) devient:
n
X h n i2
card(Acn ) = − µ(d)
d
d=2

Donc:
n
X h n i2 Xn h n i2
card(An ) = n2 + µ(d) = µ(d)
d d
d=2 d=1

D’où:
n h n i2
1X
rn = 2
µ(d)
n d
d=1

+∞ n
!
1 h n i2 1 X µ(d) X µ(d)
Comme 2 ∼ 2 on pense à montrer que: rn −→ converge absolument
n d d n→+∞ d2 d2
d=1 d=1
On a :
n n  h i 
X µ(d) X 1 n 2 1
rn − = µ(d) − 2
d2 n2 d d
d=1 d=1 !
n
1 X 1
≤ 1+2
n d
d=1
1
≤ (1 + 2(ln(n) + 1)) −→ 0
n n→+∞

5
    
1 µ(d)
Les familles et sont sommables donc:
n2 n≥1 d2 n≥1

+∞ +∞
X 1 X µ(d) X µ(d) XX µ(d) X 1 X
2 2
= 2
= = µ(d) = 1
n d (nd) l2 l2
d=1 d=1 n,d≥1 l≥1 d|l l≥1 d|l

+∞
X µ(d) 6
Ainsi = d’où :
d2 π2
d=1
6
rn −→
n→+∞ π2